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:i1] + str[i+1:N1]
is a palindrome. If it is a palindrome, we print the value of i
; otherwise, we print the value of Ni1
.
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

size_t T;
string S;
cin >> T;
while (T)
{
cin >> S;
const auto mid = begin(S) + S.size()/2;
const auto diffIt = mismatch(begin(S), mid, S.rbegin()).first;
if (diffIt != begin(S) + S.size()/2)
{
const auto diffIdx = distance(begin(S), diffIt);
if (equal(begin(S), diffIt, S.rbegin()) &&
equal(next(diffIt), mid, S.rbegin() + diffIdx))
cout << diffIdx << endl;
else
cout << S.size()  diffIdx  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
