Make Palindrome

Easy
0/40
3 upvotes
Asked in companies
MicrosoftZoho Corporation

Problem statement

You are given a string STR of length N consisting of lowercase English Alphabet letters. Your 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 to be added are 0. 

Similarly, for the given string “aabaaca”, the minimum characters needed are 2 i.e. ‘a’ and ‘c’ which makes the string “acaabaaca”, which is a 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 contains the string STR.
Output format: 
For each test case, print the count of minimum characters needed to make the string palindrome.

Output for each test case will be printed 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 <= 100 
1 <= N <= 5000 
STR contains only lowercase English letters.

Time limit: 1 second
Sample input 1:
2
abcd
dad
Sample output 1:
3
0
Explanation for Sample 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.

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, we are checking N times if the string is a palindrome. This takes linear time in each check.

Space Complexity

O(1) per test case.

 

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

Code Solution
(100% EXP penalty)
Make Palindrome
Full screen
Console