Hackerrank - Palindrome Index Solution

Hackerrank - Palindrome Index Solution.md

                        Hackerrank - Palindrome Index Solution(click on raw)

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

Hackerrank - Palindrome Index Solution.py

import sys
import math

def opt_diameter(n, m):
    count = 1
    depth = 0
    while count < n:
        depth += 1
        count = m ** depth
    return depth
    
def diameter(n, m):
    count = 1
    depth = 0
    while count < n:
        depth += 1
        count += m ** depth
    left_over = m ** depth - (count - n)
    limit = m ** (depth - 1)
    discount = 1
    if left_over > limit:
        discount = 0
    return max(depth, 2 * depth - discount)

def solve(in_file, out_file):
    n, m = (int(raw) for raw in in_file.readline().strip().split(' '))
    out_file.write("{}\n".format(opt_diameter(n, m)))
    count = 0
    for _ in range(n):
        ret = []
        for _ in range(m):
            val = count % n
            count += 1
            ret.append(str(val))
        out_file.write("{}\n".format(" ".join(ret)))

if __name__ == '__main__':
    from_file = False
    if from_file:
        path = 'Data\\'
        name = 'mega_prime'
        file_input = open(path + name + '.in', 'r')
        file_output = open(path + name + '.out','w')
        solve(file_input, file_output)
        file_input.close()
        file_output.close()
    else:
        solve(sys.stdin, sys.stdout)