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()))