How To Solve The Palindrome Index Code Challenge
How To Solve HackerRank’s Palindrome Index Code Challenge With JavaScript
Problem
Let’s break down the challenge into requirements:
- Link to challenge: HackerRank’s Palindrome Index Code Challenge
- You will receive one string, s
- s is in between 1 and 100005 inclusive
- You are allowed to remove a letter
- If if you remove a letter you must return its index
- The string after removing the letter will equal to itself backwards (a.k.a. palindrome)
- If no string is removed, or more than one character needs to be removed, return -1
// Example
"ababab"
// Result
5
// Reason, when index 5 is removed
"ababa" = "ababa" the reverseGoal
Write a function or functions that returns the index of the letter removed from string (s) in order to make it a palindrome and -1 is it not possible or no string is removed
Covering Our Bases
Making sure we meet the requirements:
function palindromeIndex (s) {
let result = -1;
const slen = s.length;
if (slen >= 1 && slen <= 100005) {
// continue code
}
return result;
}We also need to factor in if the string by itself reversed doesn’t need any characters removed to make it a palindrome.
function palindromeIndex (s) {
let result = -1;
const slen = s.length;
if (slen >= 1 && slen <= 100005 & s !== s.split('').reverse().join('')) {
// continue code
}
return result;
}Understanding The Problem
When I first attempted to solve this problem, I came up with quick solution and then refactored things to make it more efficient. HackerRank has a way of not only evaluating you on wether or not your answers are correct, but also if your code runs within the time limit, or it gives you an error and times out. I’ll be walking through my first iteration and then how I made optimizations.
Reading through the problem I knew that in order to compare the string with its reversed self, I would need to traverse it with a loop to go through each character. Essentially, remove one character at a time, compare the string and its reverse, and either return the solution or continue.
Traversing Characters
We definitely need to use a for loop to go through the characters:
function palindromeIndex (s) {
let result = -1;
const slen = s.length;
if (slen >= 1 && slen <= 100005 & s !== s.split('').reverse().join('')) {
for (let i = 0; i < slen; i++) {
// continue code
}
}
return result;
}Creating New Strings
Next we need to create new string with the character at index i remove, create its reverse and compare the string. If the string and its reverse are equal then we have a solution. Noticing that this is a for loop, we can add some optimization by adding a break to our loop once we found the answer, no need to continue going through the loop.
function palindromeIndex (s) {
let result = -1;
const slen = s.length;
if (slen >= 1 && slen <= 100005 & s !== s.split('').reverse().join('')) {
for (let i = 0; i < slen; i++) {
// create new string
let newS = s.substring(0, i) + s.substring((i + 1));
// create the reverse of that string
let revNewS = newS.split('').reverse().join('');
// compare
if (newS === revNewS) {
result = i;
break;
}
}
}
return result;
}Problems With Our First Solution
When I ran the tests most of the initial smaller values came back with the right results. The issue was when s was a length of 73785 or more. The results came back with:
Terminated due to timeoutUnderstanding The Problem Again
To understand what was needed to solve this, we need to understand what is it that we are comparing? We are comparing a string with its reverse self. We can then assume that the result we are trying to achieve is making sure it’s a palindrome, or just validating an existing palindrome. This gives an understanding that we could assume that whatever s is already a palindrome and we’re just making sure that it meets the requirements of a palindrome.
Palindrome Requirements
The requirements of a palindrome is that it reads the same forward and reversed. That means that the first letter is equal to the last letter, the second letter is equal to the second last letter, and so on. With this understanding we are essentially just comparing letters to make sure they are the same.
// Example - "acbba"↓ ↓
a c b b a = ✅same
↓ ↓
a c b b a = 🚫not the same
Comparing Letters
Refactoring our original solution from the for loop would then look like this:
function palindromeIndex (s) {
let result = -1;
const slen = s.length;
if (slen >= 1 && slen <= 100005 & s !== s.split('').reverse().join('')) {
for (let i = 0; i < slen; i++) {
// comparing the first letter with the last, etc
if (s.charAt(i) != s.charAt(len - 1 - i)) {
}
}
}
return result;
}Deciding Which Letter To Remove
Once we’ve found that out that both letters do not equal we then need to decide wether it’s the letter at the beginning or the letter at the end that needs to be remove.
// Example with for loop - "acbba"
...
i = 1
↓ ↓
a c b b a = 🚫not the same// Expected answer should be i (1)// Example with for loop - "abbca"
...
i = 1
↓ ↓
a b b c a = 🚫not the same// Expected answer should be 3 or (length - 1 - i)
We need to then evaluate both scenarios to find our answers.
function palindromeIndex (s) {
let result = -1;
const slen = s.length;
if (slen >= 1 && slen <= 100005 & s !== s.split('').reverse().join('')) {
for (let i = 0; i < slen; i++) {
// comparing the first letter with the last, etc
if (s.charAt(i) != s.charAt(slen - 1 - i)) {
// accounting for the letter at the beg.
let s1 = s.substring(0, i) + s.substring((i + 1));
// accounting for the letter at the end
let s2 = s.substring(0, (slen - 1 - i)) + s.substring((len - 1 - i) + 1);
}
}
}
return result;
}Comparing The Strings
After we have both strings, we need to compare them with their reversed version and return the respective result. Note that we are still in the for loop, so once we have the answer we can break it to skip the rest of the for loop comparing.
function palindromeIndex (s) {
let result = -1;
const slen = s.length;
if (slen >= 1 && slen <= 100005 & s !== s.split('').reverse().join('')) {
for (let i = 0; i < slen; i++) {
// comparing the first letter with the last, etc
if (s.charAt(i) != s.charAt(slen - 1 - i)) {
// accounting for the letter at the beg.
let s1 = s.substring(0, i) + s.substring((i + 1));
// accounting for the letter at the end
let s2 = s.substring(0, (slen - 1 - i)) + s.substring((len - 1 - i) + 1);
if (s1 === s1.split('').reverse().join('')) {
result = i;
break;
} else if (s2 === s2.split('').reverse().join('')) {
result = slen - 1 - i;
break;
}
}
}
}
return result;
}This already is starting to look good but we need to factor in another use-case.
What About More Than One Letter
What about the scenario that there is more than one letter that needs to be replaced. Based on the requirements, we are only allowed to remove one letter. With that, we can assume that if more than one letter is required to be removed then return -1. This is where we can add our last else to account for this.
// Example scenario - "acbdbba"...
i = 1
↓ ↓
a c b d b b a = 🚫not the same// if we removed c
"abdbba" != "abbdba"// if we removed b
"acbdba" != "abdbca"// for it to be a palindrome we would need to remove another letter
// which is out of our requirements, hence result = -1
Our code would then incorporate the last else like the following:
function palindromeIndex (s) {
let result = -1;
const slen = s.length;
if (slen >= 1 && slen <= 100005 & s !== s.split('').reverse().join('')) {
for (let i = 0; i < slen; i++) {
// comparing the first letter with the last, etc
if (s.charAt(i) != s.charAt(slen - 1 - i)) {
// accounting for the letter at the beg.
let s1 = s.substring(0, i) + s.substring((i + 1));
// accounting for the letter at the end
let s2 = s.substring(0, (slen - 1 - i)) + s.substring((len - 1 - i) + 1);
if (s1 === s1.split('').reverse().join('')) {
result = i;
break;
} else if (s2 === s2.split('').reverse().join('')) {
result = slen - 1 - i;
break;
} else {
// result is already -1 from the top
break;
}
}
}
}
return result;
}Optimizing Code Even More
There are two last optimizations we could make.
Optimizing Multiple Breaks
function palindromeIndex (s) {
let result = -1;
const slen = s.length;
if (slen >= 1 && slen <= 100005 & s !== s.split('').reverse().join('')) {
for (let i = 0; i < slen; i++) {
// comparing the first letter with the last, etc
if (s.charAt(i) != s.charAt(slen - 1 - i)) {
// accounting for the letter at the beg.
let s1 = s.substring(0, i) + s.substring((i + 1));
// accounting for the letter at the end
let s2 = s.substring(0, (slen - 1 - i)) + s.substring((len - 1 - i) + 1);
if (s1 === s1.split('').reverse().join('')) {
result = i;
} else if (s2 === s2.split('').reverse().join('')) {
result = slen - 1 - i;
}
// else is assumed
// and a break is assumed
// also accounts for result = -1
break;
}
}
}
return result;
}Optimizing For Loop
Although this isn’t really necessary because of the break, we could also assume that we do not need to traverse the entire string and only half way because we assume the string is the same forwards and reversed. We can then cut the for loop length in half:
function palindromeIndex (s) {
let result = -1;
const slen = s.length;
if (slen >= 1 && slen <= 100005 & s !== s.split('').reverse().join('')) {
for (let i = 0; i < slen / 2; i++) {
// comparing the first letter with the last, etc
if (s.charAt(i) != s.charAt(slen - 1 - i)) {
// accounting for the letter at the beg.
let s1 = s.substring(0, i) + s.substring((i + 1));
// accounting for the letter at the end
let s2 = s.substring(0, (slen - 1 - i)) + s.substring((len - 1 - i) + 1);
if (s1 === s1.split('').reverse().join('')) {
result = i;
} else if (s2 === s2.split('').reverse().join('')) {
result = slen - 1 - i;
}
// else is assumed
// and a break is assumed
// also accounts for result = -1
break;
}
}
}
return result;
}Although not necessarily needed, but it could help if we decide to factor this to remove one than one character.
Solution
The full solution without the comments:
function palindromeIndex (s) {
let result = -1;
const slen = s.length;
if (slen >= 1 && slen <= 100005 & s !== s.split('').reverse().join('')) {
for (let i = 0; i < slen; i++) {
if (s.charAt(i) != s.charAt(slen - 1 - i)) {
let s1 = s.substring(0, i) + s.substring((i + 1));
let s2 = s.substring(0, (slen - 1 - i)) + s.substring((len - 1 - i) + 1);
if (s1 === s1.split('').reverse().join('')) {
result = i;
} else if (s2 === s2.split('').reverse().join('')) {
result = slen - 1 - i;
}
break;
}
}
}
return result;
}Test Cases
Now let’s validate the code:
// "a", Expected -1
// "", Expected -1
// "acbdbba", Expected -1
// "aaab", Expected 3
// "acbba", Expected 1palindromeIndex("a"); // -1 ✅
palindromeIndex(""); // -1 ✅
palindromeIndex("acbdbba"); // -1 ✅
palindromeIndex("aaab"); // 3 ✅
palindromeIndex("acbba"); // 1 ✅
Feedback
If you have any tips on how this can be improved or discuss coding/algorithms, I would love to talk.
If you got value from this, please share it on twitter 🐦 or other social media platforms. Thanks again for reading. 🙏
Please also follow me on twitter: @codingwithmanny and instagram at @codingwithmanny.
