Problem
Given a string of lowercase letters in the range ascii[a-z], determine the index of a character that can be removed to make the string a palindrome.
Input
The first line contains an integer q, the number of queries.
Each of the next q lines contains a query string s.
Output
int: the index of the character to remove or -1 (if string s is already a palindrome)
Constraints
- 1 <= q <= 20
- 1 <= s.length() <= 105 + 5
Sample Input
3 aaab baa aaa
Sample Output
3 0 -1
Solution
Approach: Greedy Approach
The idea is to traverse the string s (s.length() = n) using a front iterator (i = 0) and a back iterator (j = n-1)
Pseudocode:
if (s[i] != s[j]):
if (s[i+1, n-1] is a palindrome):
return i
else
return j
//
// main.cpp
// Palindrome Index
//
// Created by Himanshu on 29/03/22.
//
#include <iostream>
#include <string>
using namespace std;
int main() {
string s;
int n, ans, T;
cin>>T;
while (T--) {
cin>>s;
n = (int) s.size();
ans = -1;
for (int i=0,j=n-1; i<n; i++,j--) {
if (s[i] != s[j]) {
if (s[i+1] == s[j]) {
int k = i+1, l = j;
//Checking if ith char is the required char
while (s[k] == s[l] && k < l) {
k++;
l--;
}
//if the string without ith char
// is a palindrome, ans is i, else ans is j
if (k >= l) {
ans = i;
} else {
ans = j;
}
break;
} else {
ans = j;
break;
}
}
}
cout<<ans<<endl;
}
return 0;
}
Time complexity: O(n), where n is the size of string