Skip to content
Advertisement

I am confused in a part of my python code

Q-Given a string of lowercase letters in the range ascii[a-z], determine the index of a character that can be removed to make the string a palindrome. There may be more than one solution, but any will do. If the word is already a palindrome or there is no solution, return -1. Otherwise, return the index of a character to remove.

Can anyone tell me wats happening at the s[i] != s[n-1-i] part in this code of mine.

def palindromeIndex(s):
    if s == s[::-1]:
        return -1
    
    n=len(s)
    
    for i in range(n//2):
        if s[i] != s[n-1-i]:
            if s[i:n-1-i]==s[i:n-1-i][::-1]:
                return n-1-i
            elif s[i+1:n-i]==s[i+1:n-i][::-1]:
                return i
    
    return -1

I am confused mainly in these parts

for i in range(n//2):
        if s[i] != s[n-1-i]:
            if s[i:n-1-i]==s[i:n-1-i][::-1]:
                return n-1-i
            elif s[i+1:n-i]==s[i+1:n-i][::-1]:
                return i

Advertisement

Answer

So i is the current index, iterating through the first half of the string. s[i] is the letter at that index, and s[n-1-i] will be the letter at the n-1-ith position. Since n=len(s), n-1 will be the final character in the string, and we’ll be coming backwards from there with i. For example, if we take the string foobar, and i=1, s[i] will be o and s[n-1-i] will be a. That’s the first if statement – detecting the first i at which we are no longer palindromic, that is, the ith character from the front is not the same as the ith character from the end.

Once we’ve established that this pair of characters don’t match, we need to determine if removing either one would make our string a palindrome again. There are two possible cases that would make this true:

  1. Removing the letter at n-1-i makes the string palindromic
  2. Removing the letter at i makes the string palindromic

We try these two cases in that order. However, rather than recreating the entire input string, minus one letter, we can get crafty and save memory by just testing the substring between our current endpoints for palindrome-ness instead of the entire string. After all, we know that everything outside our current in-1-i pair is already a palindrome. That’s the fancy magic you see in the if statements – testing the substrings for palindrome-ness.

s[i:n-1-i]==s[i:n-1-i][::-1] can be broken down into a couple parts. First, s[i:n-1-i] is the substring between our i and n-1-i markers, but does NOT include the letter at n-1-i. We’ll call that sub. With that substituted back in, we have sub == sub[::-1]. As you’ll recognize from earlier on in the function, that’s just how you test if a given string is a palindrome. If sub is a palindrome, then you know that, by omitting the character at n-1-i, your entire original string is palindromic. Therefore, we return n-1-i.

s[i+1:n-i]==s[i+1:n-i][::-1] breaks down much the same way. The difference is that s[i+1:n-i] is shifted one character to the right, so the result is the substring between our i and n-1-i markers, but this time NOT including the letter at s[i] and including the one at s[n-1-i]. If this substring is palindromic, then we know that it’s the letter at s[i] that has to go in order to make the original string a palindrome. Therefore, we return i

In the case where neither one of these things is true, then not only is the input string not a palindrome, but there’s no way to remove only one letter to make it one. Therefore, we return -1 to signify that there is no solution.

User contributions licensed under: CC BY-SA
6 People found this is helpful
Advertisement