Palindrome Index

See the original problem on HackerRank.

Solutions

If the string is already a palindrome, -1 is the answer since no character need be removed.

If the given string is not a palindrome, we must find one character that, once removed, will make it a palindrome. We can do this by checking if str[i] == str[N - 1 - i] where N is the length of the string for all i starting from i=0. Once this condition fails, all we have to do is to check if str[0:i-1] + str[i+1:N-1] is a palindrome. If it is a palindrome, we print the value of i; otherwise, we print the value of N-i-1.

Possible C++ implementation:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
size_t T;
cin >> T;
while (T--)
{
    string S;
    cin >> S;
    const auto mid = next(begin(S), S.length() / 2 + 1);
    const auto diffIt = mismatch(begin(S), mid, S.rbegin()).first;
    if (diffIt != mid)
    {
        const auto diffIdx = distance(begin(S), diffIt);

        if (equal(next(diffIt), mid, rbegin(S) + diffIdx))
            cout << diffIdx << endl;
        else if (equal(diffIt, mid, rbegin(s) + diffIdx + 1))
            cout << S.length() - diffIdx - 1 << endl;
        else
            cout << -1 << endl;
    }
    else
    {
        cout << -1 << endl;
    }
}

Haskell solution by Alessandro Pezzato

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
isPalindrome xs = xs == reverse xs

recPalIndex _ _ [] [] = -1
recPalIndex j i (x:xs) (y:ys) =
  if x == y
    then recPalIndex (j - 1) (i + 1) xs ys
    else if isPalindrome ((take i $ reverse $ ys) ++ xs)
           then i
           else j

palindromeIndex xs = recPalIndex (length xs - 1) 0 xs (reverse xs)

main = interact $ unlines . fmap (show . palindromeIndex) . tail . lines
We've worked on this challenge in these gyms: modena  milan 
comments powered by Disqus