Minimum Characters For Palindrome

Hard
0/120
Average time to solve is 20m
63 upvotes
Asked in companies
GeeksforGeeksBarclaysMicrosoft

Problem statement

Given a string STR of length N. The task is to return the count of minimum characters to be added at front to make the string a palindrome.

For example, for the given string “deed”, the string is already a palindrome, thus, minimum characters needed are 0.

Similarly, for the given string “aabaaca”, the minimum characters needed are 2 i.e. ‘a’ and ‘c’ which makes the string “acaabaaca” palindrome.

Detailed explanation ( Input/output format, Notes, Images )
Input format : 
The first line contains an integer 'T' which denotes the number of test cases or queries to be run. Then, the T test cases follow.

The first and only line of each test case or query contains the string STR.
Output format : 
For each test case, print the count of minimum characters needed in a separate line.

Note :

You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 10 
1 <= N <= 10 ^ 5 
STR contains only lowercase English letters.

Time limit: 1 sec
Sample input 1 :
2
abcd
dad
Sample output 1 :
3
0
Explanation of sample input 1 :
For test case 1 : 
Minimum characters to be added at front to make it a palindrome are 3 i.e. “dcb” which makes the string “dcbabcd”.  

For test case 2 :
The string is already a palindrome, we do not need to add any character.
Sample input 2 :
2
xxaxxa    
abb
Sample output 2 :
1
2
Hint

First off, observe that the question focuses on the terms palindrome and addition at front. We have to make a string a palindrome when we are allowed to add characters only at front.

Approaches (2)
Brute Force
  • The idea is pretty simple, as we can add only at the front, thus, we need to work on the prefix of the string.
  • We need to find the largest prefix that is a palindrome. For example, in case of “abbac”, the largest prefix that is a palindrome is “abba”, now all you need to do is add the reverse of left out suffix i.e. “ca” at the front to make it a palindrome.
  • This can be done in the following way:-
    • Until the string becomes a palindrome:
      • Remove the last character from the string.
    • Once the string becomes a palindrome or empty:
      • Subtract the current length of string with the actual length of the string and return the function.
  • In the case of “xxaxxxr” of length 7:
    As, “xxaxxxr” is not a palindrome, remove the last character, the new string will be “xxaxxx”
    As, “xxaxxx” is not a palindrome either, remove the last character, the new string will be “xxaxx”. 
    Now, as, “xxaxx” is a palindrome:
    Answer = actual length - current length
    Answer = 7 - 5 i.e. 2.
Time Complexity

O(N ^ 2) per test case, where N is the size of the given string. 

 

In the worst case, for N number of times, we are checking if the string is a palindrome of not taking O(N) time.

Space Complexity

O(1) per test case,

 

In the worst case, only constant extra space is used. 

Video Solution
Unlock at level 3
(75% EXP penalty)
Code Solution
(100% EXP penalty)
Minimum Characters For Palindrome
Full screen
Console