• Posts

Problem 214 Shortest Palindrome

Problem Statement

Link - Problem 214

Question

You are given a string s. You can convert s to a palindrome by adding characters in front of it.

Return the shortest palindrome you can find by performing this transformation.

Example 1:

Input: s = "aacecaaa"
Output: "aaacecaaa"

Example 2:

Input: s = "abcd"
Output: "dcbabcd"

Constraints:

• 0 <= s.length <= 5 * 104
• s consists of lowercase English letters only.

Solution

class Solution {
public:
    string shortestPalindrome(string s) {
        int size = s.size();
        if(size == 0){
            //cout<<s<<endl;
            return s;
        }

        int l =0, r;
        for(r =size-1; r>=0; r--){
            if(s[r]==s[l])
                l++;
        }

        if(l == size){
            //cout<<s<<endl;
            return s;
        }

        string rightnonmatch = s.substr(l,size);
        string reverseprepend = string(rightnonmatch.rbegin(),rightnonmatch.rend());

        //cout<<"nonmatchsuffix "<<rightnonmatch<<" reversedsuffix "<<reverseprepend<<endl;

        string ans = reverseprepend + shortestPalindrome(s.substr(0,l)) + rightnonmatch;
        //cout<< ans<<endl;
        return ans;
    }
};

Complexity Analysis

| Algorithm     | Time Complexity | Space Complexity |
| ------------- | --------------- | ---------------- |
| Recursive KMP | O(n log n)      | O(n)             |

Explanation

Intial Thoughts

To approach this problem, consider the concept of a palindrome and how it can be achieved by adding characters to the front of a given string. Think about how to identify the non-matching part of the string that needs to be mirrored. Consider the idea of comparing characters from both ends of the string and moving towards the center. Think about how to handle the case when the input string is already a palindrome. Identify key factors such as the length of the string and the concept of reversal.

Intuitive Analysis

Intuitively, to find the shortest palindrome, start by comparing characters from the beginning and end of the string, moving inwards. When a mismatch is found, reverse the non-matching part and prepend it to the original string, but also consider the part of the string before the mismatch. Think of the process as folding the string in half and then adjusting the non-matching parts to create a palindrome. Consider how this process can be applied recursively to handle different cases. Consider how to handle the remaining part of the string after reversing the non-matching part. Think about how to combine these insights to form an efficient solution.

1. Intuition

• The problem requires finding the shortest palindrome by adding characters to the front of the input string s
• To achieve this, we need to identify the longest prefix of s that is also a suffix, as this will help in minimizing the number of characters to be added
• The approach involves comparing characters from the start and end of the string s and moving towards the center
• If a mismatch is found, we need to add the non-matching suffix to the front of the string in reverse order
• This process is recursive, as we need to ensure the resulting string is also a palindrome
• The key insight is to use the recursive function shortestPalindrome to handle the non-matching suffix and the remaining part of the string
• The algorithmic choice of using recursion allows for a clean and efficient solution
• The time complexity of this approach is O(n), where n is the length of the input string s

2. Implementation

• The solution starts by checking the base case where the input string s is empty, in which case it returns s as it is
• It then initializes two pointers l and r to the start and end of the string s, respectively, and moves them towards the center while comparing characters
• When a mismatch is found, it extracts the non-matching suffix using s.substr(l, size) and reverses it using string(rightnonmatch.rbegin(), rightnonmatch.rend())
• The recursive call to shortestPalindrome is made with the substring s.substr(0, l) to handle the remaining part of the string
• The final result is constructed by concatenating the reversed non-matching suffix, the result of the recursive call, and the non-matching suffix using reverseprepend + shortestPalindrome(s.substr(0, l)) + rightnonmatch
• The use of rbegin() and rend() allows for easy reversal of the non-matching suffix
• The recursive approach ensures that the resulting string is the shortest possible palindrome

Complexity Analysis

Time Complexity:

• The time complexity is primarily driven by the recursive calls to shortestPalindrome and the substr operation. The substr operation takes O(k) time where k is the length of the substring. The recursive calls have a depth of O(log n) due to the divide-and-conquer approach, where n is the size of the input string s. Considering the reverseprepend operation takes O(k) time where k is the length of rightnonmatch, the overall time complexity is O(n log n).
• The dominant operations are the recursive calls, substring creation using substr, and the reversal of rightnonmatch using rbegin and rend. Each of these takes linear time in terms of the size of their input, and due to the recursive nature, this leads to a logarithmic factor in the overall time complexity.
• Justifying the Big O classification as O(n log n) stems from analyzing the recursion tree and the operations within each recursive call. The recursion depth is O(log n) due to the nature of the problem division, and within each level of recursion, operations like substr and reversal contribute to the linear factor, thus resulting in O(n log n) time complexity.

Space Complexity:

• The space complexity is influenced by the recursion stack, the creation of new strings (reverseprepend, rightnonmatch, and ans), and the input string s. The recursion stack can go as deep as O(log n) levels due to the recursive calls.
• Data structures like the input string s and the creation of new strings at each recursive level contribute to the space complexity. The substr operation creates new strings, but these are not stored beyond the scope of the recursive calls, thus not contributing to an exponential space growth.
• Justification of the space complexity as O(n) comes from considering the maximum depth of the recursion tree and the maximum size of strings created at any level of recursion, which does not exceed O(n) due to the problem’s constraints and the nature of string manipulation.

Footnote

This question is rated as Hard difficulty.

Similar Questions: