# 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; } } 

  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