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.

HackerRank Problem Link

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

Leave a Reply