# Palindrome Index | HackerRank Solution [Easy]

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