Hackerrank - Palindrome Index Solution

# Hackerrank - Palindrome Index Solution

Given a string of lowercase letters in the range ascii[a-z], determine a character that can be removed to make the string a palindrome. There may be more than one solution, but any will do. For example, if your string is "bcbc", you can either remove 'b' at index  or 'c' at index . If the word is already a palindrome or there is no solution, return -1. Otherwise, return the index of a character to remove.

Function Description

Complete the palindromeIndex function in the editor below. It must return the index of the character to remove or .

palindromeIndex has the following parameter(s):

• s: a string to analyze

Input Format

The first line contains an integer , the number of queries.
Each of the next  lines contains a query string .

Constraints

• All characters are in the range ascii[a-z].

Output Format

Print an integer denoting the zero-indexed position of the character to remove to make  a palindrome. If  is already a palindrome or no such character exists, print .

Sample Input

3
aaab
baa
aaa


Sample Output

3
0
-1


Explanation

Query 1: "aaab"
Removing 'b' at index  results in a palindrome, so we print  on a new line.

Query 2: "baa"
Removing 'b' at index  results in a palindrome, so we print  on a new line.

Query 3: "aaa"
This string is already a palindrome, so we print . Removing any one of the characters would result in a palindrome, but this test comes first.

Note: The custom checker logic for this challenge is available here.

### Solution in Python

def palindromeIndex(s):
l = len(s)
i = 0
j = l-1
while i<l:
if s[i]!=s[j]:
break
i+=1
j-=1
if i>j: return -1
a = i+1
b = j
while a<j and b>i+1:
if s[a]!=s[b]:
return j
a+=1
b-=1
return i

for _ in range(int(input())):
print(palindromeIndex(input()))

Logic explanation

Let our string be

s = "babi7loolibab"

Our code is

l = len(s)
i = 0
j = l-1
while i<l:
if s[i]!=s[j]:
break
i+=1
j-=1
if i>j: return -1

In the above part we are comparing string from forward to backward, if i becomes greater than j it will simply mean that out string is a palindrome. Therefore we return -1

a = i+1
b = j
while a<j and b>i+1:
if s[a]!=s[b]:
return j
a+=1
b-=1
return i

But in our example string s = "babi7loolibab" our loop will break when i=4 and j = 8.

It means we have to remove index 4 or index 8.

So we just have to check if s[i+1:8] is a palindrome or not.

If yes we will return i else we will return j

Alternative solution

def palindromeIndex(s):
for i,j in enumerate(range(0,len(s)//2),1):
if s[-i] == s[j]:
continue
if s[j:-i]==s[j:-i][::-1]:
return len(s)-i
elif s[j+1:-i+1]==s[j+1:-i+1][::-1]:
return j
return -1
return -1

for _ in range(int(input())):
print(palindromeIndex(input()))