Shortest Palindrome

Moderate
0/80
Average time to solve is 24m
profile
Contributed by
9 upvotes
Asked in companies
Goldman SachsDunzoNsquare

Problem statement

You are given a string ‘STR’. Your task is to find the shortest palindrome that can be formed by adding characters in front of ‘STR’.

For example: 
You are given ‘STR’ = “aabcd”. Then our answer will be “dcbaabcd”. We can form a palindrome by adding ‘d’, ‘c’, and ‘b’ in front of ‘STR’.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains an integer 'T' which denotes the number of test cases.

The first line of each test case contains a string denoting the input string.
Output Format: 
For each test case, print the shortest palindrome that can be formed by adding characters in front of ‘STR’.

The output of each test case will be printed in a separate line.
Constraints: 
1 <= T <= 10 
1 <= STR.LENGTH  <= 5000
‘STR’ contains only lowercase English letters.

Time limit: 1 sec
Note: 
You do not need to input or print anything, as it has already been taken care of. Just implement the given function.
Sample Input 1:
2
aabcd
abad
Sample Output 1:
dcbaabcd
dabad
Explanation:
For the first test case, you are given ‘STR’ = “aabcd”. Then our answer will be “dcbaabcd”. We can form a palindrome by adding ‘d’, ‘c’, and ‘b’ in front of ‘STR’.

For the second test case, you are given ‘STR’ = “abad”. Then our answer will be “dabad”. We can form a palindrome by adding ‘d’ in front of ‘STR’.
Sample Input 2:
2
abda
acbbca
Sample Output 2:
adbabda
acbbca
Hint

Find the palindromic substring of the input string.

Approaches (3)
Brute Force

In this approach, we will find the largest palindromic substring of ‘STR’ from the beginning, and we will reverse the remaining substring of ‘STR’ and append it to the beginning of ‘STR’.

5454545

Let’s write ‘STR’ as ‘PSTR’ + ‘RSTR’, where ‘PSTR’ is the palindromic substring of ‘STR’ and ‘RSTR’ is the remaining substring of ‘STR’. Then our answer would be REVERSE(‘RSTR’) + ‘STR’.5454545
 

Algorithm:

  • Initialize a variable 'REV' to store the reverse of 'STR'.
  • Initialize a variable 'N' to store the length of 'STR'.
  • Iterate 'I' in 0 to 'N':
    • If the substring of 'REV' from index 'I' is equal to the substring of 'STR' up to index 'I':
      • Return the substring of 'REV' up to index 'I' append with 'STR'.
  • Return empty character if the palindrome cannot be formed.
Time Complexity

O(N ^ 2), where N is the length of the input string ‘STR’.

 

We are iterating from 0 to N, and in each iteration, we compare two strings of linear size. Comparing two strings of linear length takes O(N) time. Hence, the overall time complexity will be O(N ^ 2).

Space Complexity

O(N), where N is the length of the input string ‘STR’.

 

The extra space is used to store the reverse of the input string ‘STR’. The size of string ‘REV’ is N. Hence, the overall space complexity is O(N).

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