How To Solve The Palindrome Index Code Challenge

How To Solve The Palindrome Index Code ChallengeHow To Solve HackerRank’s Palindrome Index Code Challenge With JavaScriptManny CodesBlockedUnblockFollowFollowingFeb 12How To Solve HackerRank’s Palindrome Index Code Challenge With JavaScriptProblemLet’s break down the challenge into requirements:Link to challenge: HackerRank’s Palindrome Index Code ChallengeYou will receive one string, ss is in between 1 and 100005 inclusiveYou are allowed to remove letterIf if you remove a letter you must return its indexThe 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"// Result5// Reason, when index 5 is removed"ababa" = "ababa" the reverseGoalWrite 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 removedCovering Our BasesMaking 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 ProblemWhen 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 not only evaluating you on wether or not your answers are correct, but also if your code run 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 CharactersWe 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 StringsNext 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 SolutionWhen 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 AgainTo 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 RequirementsThe 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 sameComparing LettersRefactoring 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 RemoveOnce 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 StringsAfter 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 LetterWhat 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 = -1Our 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 MoreThere are two last optimizations we could make.

Optimizing Multiple Breaksfunction 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 LoopAlthough 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.

SolutionThe 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 CasesNow 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 ✅FeedbackIf 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: @mannycoding and instagram at @mannycodes.

.

. More details

Leave a Reply