# Index of letter removed to make string palindrome

This code finds the index in the string and removes the one which will make the string a palindrome. If the string is already a palindrome, it should return -1.

This code works correct, but I am looking for a better implementation of it. Here is the problem description.

def palindrome(string):
return string == string[::-1]

def palindrome_index(string, start, end):
while start < end:
if string[start] == string[end]:
start, end = start+1, end-1
continue
if palindrome(string[start:end]): return end
return start
return -1
N = input()
strings = [str(raw_input()) for _ in range(N)]
for string in strings:
print palindrome_index(string, 0, len(string)-1)


Can this be written shorter? The size of input strings can be as large as 105, hence a recursive approach won't work.

## Flow

The continue and returns inside the while loop make me feel the loop is doing too much. I would say that the loop should be for moving start and end and then put the logic outside of it:

while ( start < end and string[start] == string[end] ):
start, end = start + 1, end - 1

# now figure out the result


## Result

The problem states that all strings that are not already palindromes are only off by one character.

Our loop moved start and end such that if start == end, then the string is a palindrome. It has also moved these indices such that if the string is not a palindrome, one of them is 'pointing' to the character that needs to be removed.

To figure out which index is correct, I chose to compare the character pointed to by start to the character pointed to by end - 1.

if ( start == end ):
return -1
elif ( string[ start ] == string[ end - 1 ] ):
return end
else:
return start


## Palindrome Function

You don't need this function at all because we know that if the string is not a palindrome, it is only off by one character. We were able to figure out the index of this character just by moving start and end

Anyway, since the function returns a boolean, it should be named isPalindrome

• string[ start ] == string[ end - 1 ] does not cover all the test cases, you need to out another check like string[start+1] == string[end-2] Take 'abaab' for example. – Anubhav Agarwal Sep 20 '14 at 8:55