Solution For Shortest Palindrome

Problem Statement:

Given a string s, you can add at most one character to it in order to make it a palindrome.

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

Input:

The input consists of a single string s containing lowercase English letters.

Output:

Return a string representing the shortest palindrome that can be formed from s by adding at most one character.

Constraints:

1 <= s.length <= 10^5
s consists of lowercase English letters.

Solution:

In order to solve this problem, we can follow the below approach:

1. Start comparing the characters of the string from the start and end simultaneously. If they are same, then move ahead.

2. If the characters are different, then we can make the string palindrome by adding one character either to the start or the end of the string.

3. We will then start comparing the new string obtained after adding the character from the new start and end.

4. If the characters at the new start and new end are same, then move ahead.

5. If they are different, then we can again make the string palindrome by adding one more character either to the start or end of the new string.

6. Repeat this process until we get a palindrome.

Example:

Input: s = “abcd”

Output: “dcbabcd”

Explanation: We can add ‘dcb’ to the start of the string to make it a palindrome. So the resultant palindrome string will be “dcbabcd”.

Code:

We can implement the above approach using the code below:

class Solution {
public:
string shortestPalindrome(string s) {
int l = 0, r = s.size() – 1, n = s.size();
while (r >= 0) {
if (s[l] == s[r]) {
l++;
r–;
} else {
r–;
n++;
}
}
string res(n, 0);
for (int i = n – 1; i >= 0; i–) {
if (i < l)
res[i] = s[n – i – 1];
else if (i >= l && i <= r)
res[i] = s[i];
else
res[i] = s[n – i – 1];
}
return res;
}
};

Time Complexity:

The time complexity of the above solution is O(n^2), where n is the length of the input string.

Step by Step Implementation For Shortest Palindrome

public class Solution {
    public String shortestPalindrome(String s) {
        int j = 0;
        for (int i = s.length() - 1; i >= 0; i--) {
            if (s.charAt(i) == s.charAt(j)) { j += 1; }
        }
        if (j == s.length()) { return s; }
        String suffix = s.substring(j);
        return new StringBuffer(suffix).reverse().toString() + shortestPalindrome(s.substring(0, j)) + suffix;
    }
}

def shortestPalindrome(self, s: str) -> str:
        r = s[::-1]
        for i in range(len(s) + 1):
            if s.startswith(r[i:]):
                return r[:i] + s

var shortestPalindrome = function(s) {
    // your code goes here
};

class Solution {
public:
    string shortestPalindrome(string s) {
        int n = s.size();
        int i = 0, j = n - 1;
        while (j >= 0) {
            if (s[i] == s[j]) {
                i++;
            }
            j--;
        }
        if (i == n) {
            return s;
        }
        string suffix = s.substr(i);
        reverse(suffix.begin(), suffix.end());
        return suffix + shortestPalindrome(s.substr(0, i)) + s.substr(i);
    }
};

public class Solution {
    public string ShortestPalindrome(string s) {
        // check if string is already a palindrome
        bool isPalindrome = true;
        for (int i = 0; i < s.Length / 2; i++) {
            if (s[i] != s[s.Length - 1 - i]) {
                isPalindrome = false;
                break;
            }
        }
        if (isPalindrome) {
            return s;
        }
        
        // find longest palindromic suffix
        int longestPalindromicSuffixLength = 0;
        for (int i = s.Length - 1; i >= 0; i--) {
            bool isPalindrome = true;
            for (int j = 0; j < s.Length - i; j++) {
                if (s[i + j] != s[s.Length - 1 - j]) {
                    isPalindrome = false;
                    break;
                }
            }
            if (isPalindrome) {
                longestPalindromicSuffixLength = s.Length - i;
                break;
            }
        }
        
        // add characters to the beginning of the string to make it a palindrome
        for (int i = s.Length - 1; i >= longestPalindromicSuffixLength; i--) {
            s = s[i] + s;
        }
        
        return s;
    }
}