Palindrome-related questions are generally asked in interviews because they require a strong understanding of string manipulation and recursion. A palindrome is a string that is the same as if you reverse that string. For example, string s = “abcba” is a palindrome string read as from front and backward. One of the most common coding problems is “shortest palindrome”, which we are going to solve here.
What is The “Shortest Palindrome” Problem?
As the name suggests, in the Shortest Palindrome problem, you are given a string, and you have to find the shortest Palindrome string from the given string by adding characters in the front.
For example, s = “abac” here you have to add ‘c’ at the front of the string to make it palindrome. So the resultant string would be res = “cabac”.The string x = “cabaabac” is also plainrom, but its size is not minimum, so it is not the shortest palindrome of the string s.
Brute Force Approach
Let’s start with Brute Force. In this approach, we will create all the possible substrings of index 0. We find out the longest substring starting from index 0 which is palindrome. After finding it, we find the substring of size (n – size of longest substring). Starting from the size of the longest substring. We will reverse the resultant substring and add this to our main string.
Let’s examine this approach step by step.
- Create two variables j = n-1 and curr = n-1. They will take care of the current index, where n is the size of the string.
- Iterate over the string from i = 0 to i< n/2. Now check if s[i] == s[j] or not.
- If not, then update j = curr – 1, curr = j, i = 0. And start repeating the same process.
- If s[i] == s[j], then update j = j-1 and continue the process.
- Once we have completed the loop, we will create a reverse string rev = reverse of s. Now find the substring from the string rev.
- The substring will start from index 0 and of length (n-curr).
- Now, we will add this substring to string s and return this new string.
The time complexity for the above code is O(n^2) as we are finding all the substrings starting from index 0. It will take O(n^2) time. The space complexity is O(1) as we are not using any extra space.
Optimized Approach
In the above approach, we are taking too much time. We can reduce it if we use the KMP algorithm here. The basic idea is that we will find the longest palindromic prefix. We will find this by adding ‘#’ and the reverse string of the given string to the back of the given string. Now, we’ll find the longest palindromic substring.
Let’s examine this approach step by step.
- First, create a reverse string of the given string. Now create another string having value s + ‘#’ + reverse of s.
- Now call the function longest_prefix by passing this newly created string.
- Inside the function, you need to create a vector v that will store the longest prefix for each index. Assign this with 0. Create a length variable that will keep track of the previous longest prefix length.
- Now call the while loop and keep on iterating till i<n.
- Now check if s[length] == s[i]. If it is, then update v[i++] == ++lenght.
- If it is not then check if the length is 0 or not. If it is not 0, then update length = v[length-1]. If the length is 0, then update v[i++] = 0.
- At last return v[n-1].
Let’s do in our favorite programming languages.
C++ Code
Here is the C++ solution to the shortest palindrome problem:
#include<bits/stdc++.h>
using namespace std;
int longest_prefix(string& s)
{
int n = s.length();
vector<int> v(n, 0); // initialized with 0
int length = 0; // length of previous longest prefix suffix
// the loop calculates v[i] for i = 1 to M-1
int i = 1;
while (i < n) {
if (s[length] == s[i]) {
v[i++] = ++length;
}
else {
if (length != 0)
length = v[length - 1];
else
v[i++] = 0;
}
}
return v[n - 1];
}
int main(){
string s = "abvbakjjka";
string rev = s;
reverse(rev.begin(),rev.end());
string temp = s + '#' + rev;
int len = longest_prefix(temp);
int n = s.size();
string res = rev.substr(0, n - len);
res = res + s;
cout<<res<<endl;
return 0;
}Java Code
Let’s solve it in Java too:
import java.util.*;
public class Main {
static int longestPrefix(String s) {
int n = s.length();
int[] v = new int[n]; // initialized with 0
int length = 0; // length of previous longest prefix suffix
// the loop calculates v[i] for i = 1 to M-1
int i = 1;
while (i < n) {
if (s.charAt(length) == s.charAt(i)) {
v[i++] = ++length;
} else {
if (length != 0)
length = v[length - 1];
else
v[i++] = 0;
}
}
return v[n - 1];
}
public static void main(String[] args) {
String s = "abvbakjjka";
StringBuilder rev = new StringBuilder(s);
rev.reverse();
String temp = s + '#' + rev;
int len = longestPrefix(temp);
int n = s.length();
String res = rev.substring(0, n - len) + s;
System.out.println(res);
}
}Python Code
Here is the same implementation in Python:
def longest_prefix(s): n = len(s) v = [0] * n # initialized with 0 length = 0 # length of previous longest prefix suffix # the loop calculates v[i] for i = 1 to M-1 i = 1 while i < n: if s[length] == s[i]: v[i] = length + 1 length += 1 i += 1 else: if length != 0: length = v[length - 1] else: v[i] = 0 i += 1 return v[n - 1] if __name__ == "__main__": s = "abvbakjjka" rev = s[::-1] temp = s + '#' + rev length = longest_prefix(temp) n = len(s) res = rev[:n - length] + s print(res)
Output:
akjjkabvbakjjkaThe time complexity for the above code is O(n) as we are just iterating the string once. The space complexity for the above code is O(n) as we are using a vector of size n.
Analysis of Both Approaches
| Approach | Time Complexity | Space Complexity | Description |
|---|---|---|---|
| Brute Force | O( n^2 ) | O(1) | As we are finding all the substrings starting from index 0, whose time complexity is O(n^2) |
| Optimized Approach | O(n) | O(n) | We are just storing the values of the longest prefix from each index in a vector and because of this, the space complexity goes to O(n). |
Conclusion
In this article, we discussed various approaches to solving the “Shortest Palindrome” question. We have seen that the brute force approach is taking O(n^2) time complexity as we are finding all the substring that starts from index 0. We also see how we can optimize the above approach by storing the longest prefix for all the indexes. You can also try some more questions like “Longest Palindromic Substring,” and “Maximum Deletions on a String” etc.
