Leetcode 214. Shortest Palindrome

Problem Explanation:

A palindrome is a string that reads the same forwards and backwards. For example, "racecar" is a palindrome. Given a string s, the task is to convert this string into a palindrome by adding characters in front of the original string. The goal is to find the shortest possible palindrome that can be created using this process.

For example, if the input is "abcd", a palindrome can be created by adding the characters "dcb" in front of it resulting in "dcbabcd". Similarly, if the input is "aacecaaa", we only need to add an "a" at the beginning to get "aaacecaaa".

Solution Approach:

The solution uses the reverse and substring functions to solve this problem. It starts by creating a reversed copy of the original string. Then, it takes substrings of the original and the reversed string. Starting from the entire length of the string - i (where i starts from 0), it finds the substring of the original string and cross verifies it with the substring of the reversed string starting from i.

This process continues until we find two substrings that match. When it finds a match, it knows that the substring of the reversed string is the minimum sequence of characters that need to be added at the front to make the original string a palindrome. We then return this sequence concatenated to the original string.

Solution in Different Programming Languages:

Python Solution:

1
2python
3class Solution:
4    def shortestPalindrome(self, s: str) -> str:
5        t = s[::-1]
6        n = len(s)
7        
8        for i in range(n):
9            if s[:n - i] == t[i:]:
10                return t[:i] + s
11        return t + s

Java Solution:

1
2java
3public class Solution {
4    public String shortestPalindrome(String s) {
5        String t = new StringBuilder(s).reverse().toString();
6        int n = s.length();
7        
8        for (int i = 0; i < n; i++) {
9            if (s.substring(0, n - i).equals(t.substring(i))) {
10                return t.substring(0, i) + s;
11            }
12        }
13        
14        return t + s;
15    }
16}

JavaScript Solution:

1
2javascript
3class Solution {
4    shortestPalindrome(s) {
5        let t = s.split('').reverse().join('');
6        let n = s.length;
7        
8        for (let i = 0; i < n; i++) {
9            if (s.substring(0, n - i) === t.substring(i)) {
10                return t.substring(0, i) + s;
11            }
12        }
13        
14        return t + s;
15    }
16}

C++ Solution:

1
2cpp
3class Solution {
4public:
5    string shortestPalindrome(string s) {
6        string t = s;
7        reverse(t.begin(), t.end());
8        int n = s.length();
9        
10        for (int i = 0; i < n; i++) {
11            if (s.substr(0, n - i) == t.substr(i)) {
12                return t.substr(0, i) + s;
13            }
14        }
15        
16        return t + s;
17    }
18};

C# Solution:

1
2csharp
3public class Solution {
4    public string ShortestPalindrome(string s) {
5        string t = new string(s.Reverse().ToArray());
6        int n = s.Length;
7        
8        for (int i = 0; i < n; i++) {
9            if (s.Substring(0, n - i) == t.Substring(i)) {
10                return t.Substring(0, i) + s;
11            }
12        }
13        
14        return t + s;
15    }
16}

Explanation of the Code:

The solution starts by creating a reversed copy of the string using the reverse(). It then cycles through all possible lengths of a prefix, starting from the longest to the shortest, checking if this segment is a palindrome. Once it finds a palindrome, it returns that prefix plus the original string. If no segment matching these conditions is found, the code concatenates a reversed copy of the original string to the front of the original string.This solution is efficient and runs in linear time complexity. We don't need a nested loop because we are just doing a single pass through the string. In each iteration, we only need to check a suffix of the reversed string against a prefix of the original string.

Walkthrough of the Code:

• Let us take an example string "abcd".

• The solution starts by reversing the original string resulting in t="dcba".

• Then, an iteration begins where i loops through indices 0 to n-1 where n is the length of string s.

• In each iteration, it checks if a substring of original string s[:n - i] is equal to substring of reversed string t[i:].

  • During first iteration (When i = 0), it checks if "abcd" = "dcba" , which is False. So, it moves to the next iteration.

  • During the second iteration (When i = 1), it checks if "abc" = "cba", which is again False. So, it moves to the next iteration.

  • During the third iteration (When i = 2), it checks if "ab" = "ba" , which is again False. So, it moves to the next iteration.

  • During the fourth iteration (When i = 3), it checks if "a" = "a" , which is True. So, it stops and attaches the substring t[:i] i.e. "dcb" in front of original string, resulting "dcb"+"abcd" = "dcbabcd".

• As it found a match, it returns "dcbabcd" which is the shortest palindrome that can be made by adding characters in front.

If no such suffix and prefix were found to be equal during the iterations, it would return the reversed string appended to the original string as the result.

This approach works because any palindrome can be split into two halves that are mirror images of each other. Therefore, by checking prefixes against reverses of suffixes, we're effectively searching for the longest palindrome that exists at the start of the string, after which the remainder can be reversed and appended to the front to create the final palindrome.