Question

Formatted question description: https://leetcode.ca/all/214.html

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 * 10⁴
s consists of lowercase English letters only.

Algorithm

In the worst-case scenario, where there are no identical characters in the string s, the minimum number of characters required to be added is s.size() - 1.
In the first example, the string contains a palindrome. To form a complete palindrome, only one character needs to be added to the front.

To solve this, first reverse the string s to obtain t. Then, compare the original string s with the reversed string t, starting from the first character and proceeding one character at a time:

If they are equal, it indicates that s is already a palindrome. No additional characters need to be added, and the function can return immediately.
If they are not equal, remove the last character from s, remove the first character from t, and continue comparing. This process repeats until the strings are equal or the loop concludes.

This method ensures that the two strings are concatenated in the correct manner to form a palindrome.

Examples:

Worst Case: “abcda”+”adcba”

Reversed:  a b c d a
s:                   a d c b a

Try to move both towards the center to find a possible overlap. By removing one character, we save an “a”.

Reversed:  a b c d a
s:                 a d c b a

Move further, “da” and “ad” overlap, and the remaining part, “abc” vs “cba”, forms a palindrome.

Reversed:  a b c d a
s:               a d c b a

Therefore, “da” and “ad” go to the next recursion.

Reversed:  d a
s:             a d

Moving one more character aligns the strings perfectly, yielding the final result.

“abc”+dfs()+”cba” => “abc”+”dad”+”cba”
```
Reversed:  d a
s:           a d
```

Another Example: “aacecaaa”

The iteration stops at the last ‘a’, i=7.
"a"+dfs("aacecaa")+"a"

This approach strategically reduces the problem size by identifying overlapping parts between the original and reversed strings, effectively minimizing the number of characters needed to transform the input into a palindrome.

Code

public class Shortest_Palindrome {


    public class Solution {
        public String shortestPalindrome(String s) {

            if (s == null || s.length() == 0) {
                return "";
            }

            int i = 0, n = s.length();
            for (int j = n - 1; j >= 0; --j) { // @note: j will cross i, eg. making i=2 for "adcba"
                if (s.charAt(i) == s.charAt(j)) {
                    ++i;
                }
            }
            // now [0, i) is a possible palindrome, but need extra check
            if (i == n) {
                return s;
            }

            String remaining = s.substring(i); // need to add reverse part of it
            String rem_rev = new StringBuilder(remaining).reverse().toString();
            return rem_rev + shortestPalindrome(s.substring(0, i)) + remaining;

        }
    }
}

############

class Solution {
    public String shortestPalindrome(String s) {
        int base = 131;
        int mul = 1;
        int mod = (int) 1e9 + 7;
        int prefix = 0, suffix = 0;
        int idx = 0;
        int n = s.length();
        for (int i = 0; i < n; ++i) {
            int t = s.charAt(i) - 'a' + 1;
            prefix = (int) (((long) prefix * base + t) % mod);
            suffix = (int) ((suffix + (long) t * mul) % mod);
            mul = (int) (((long) mul * base) % mod);
            if (prefix == suffix) {
                idx = i + 1;
            }
        }
        if (idx == n) {
            return s;
        }
        return new StringBuilder(s.substring(idx)).reverse().toString() + s;
    }
}

// OJ: https://leetcode.com/problems/shortest-palindrome/
// Time: O(N)
// Space: O(1) ignoring the space taken by the answer
class Solution {
public:
    string shortestPalindrome(string s) {
        unsigned d = 16777619, h = 0, rh = 0, p = 1, maxLen = 0;
        for (int i = 0; i < s.size(); ++i) {
            h = h * d + s[i] - 'a';
            rh += (s[i] - 'a') * p;
            p *= d;
            if (h == rh) maxLen = i + 1;
        }
        return string(rbegin(s), rbegin(s) + s.size() - maxLen) + s;
    }
};

'''
reversed(): returns a reverse iterator

>>> s = "aabbcc"
>>> reversed(s)
<reversed object at 0x108384a60>
>>> ''.join(reversed(s))
'ccbbaa'


>>> s = "aabbcc"
>>> s[::-1]
'ccbbaa'
'''
class Solution:
    def shortestPalindrome(self, s: str) -> str:
        if not s:
            return ""

        i, n = 0, len(s)
        for j in range(n - 1, -1, -1):
            if s[i] == s[j]:
                i += 1

        if i == n:
            return s

        remaining = s[i:]
        rem_rev = remaining[::-1]
        return rem_rev + self.shortestPalindrome(s[:i]) + remaining

############

class Solution:
    def shortestPalindrome(self, s: str) -> str:
        base = 131
        mod = 10**9 + 7
        n = len(s)
        prefix = suffix = 0
        mul = 1
        idx = 0
        for i, c in enumerate(s):
            prefix = (prefix * base + (ord(c) - ord('a') + 1)) % mod
            suffix = (suffix + (ord(c) - ord('a') + 1) * mul) % mod
            mul = (mul * base) % mod
            if prefix == suffix:
                idx = i + 1
        return s if idx == n else s[idx:][::-1] + s

############

class Solution(object):
  # brutal force TLE
  def _shortestPalindrome(self, s):
    """
    :type s: str
    :rtype: str
    """

    def isPal(cand):
      start, end = 0, len(cand) - 1
      while start < end:
        if cand[start] != cand[end]:
          return False
        start += 1
        end -= 1
      return True

    n = len(s)
    ans = s[::-1] + s
    ansLen = 2 * len(s)
    for i in reversed(range(0, len(s) + 1)):
      newPal = s[i:][::-1] + s
      if isPal(newPal) and n + len(s) - i < ansLen:
        ansLen = n + len(s) - i
        ans = newPal
    return ans

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

func shortestPalindrome(s string) string {
	n := len(s)
	base, mod := 131, int(1e9)+7
	prefix, suffix, mul := 0, 0, 1
	idx := 0
	for i, c := range s {
		t := int(c-'a') + 1
		prefix = (prefix*base + t) % mod
		suffix = (suffix + t*mul) % mod
		mul = (mul * base) % mod
		if prefix == suffix {
			idx = i + 1
		}
	}
	if idx == n {
		return s
	}
	x := []byte(s[idx:])
	for i, j := 0, len(x)-1; i < j; i, j = i+1, j-1 {
		x[i], x[j] = x[j], x[i]
	}
	return string(x) + s
}

// https://leetcode.com/problems/shortest-palindrome/

using System.Text;

public partial class Solution
{
    public string ShortestPalindrome(string s)
    {
        for (var i = s.Length - 1; i >= 0; --i)
        {
            var k = i;
            var j = 0;
            while (j < k)
            {
                if (s[j] == s[k])
                {
                    ++j;
                    --k;
                }
                else
                {
                    break;
                }
            }
            if (j >= k)
            {
                var sb = new StringBuilder(s.Length * 2 - i - 1);
                for (var l = s.Length - 1; l >= i + 1; --l)
                {
                    sb.Append(s[l]);
                }
                sb.Append(s);
                return sb.ToString();
            }
        }

        return string.Empty;
    }
}

impl Solution {
    pub fn shortest_palindrome(s: String) -> String {
        let base = 131;
        let (mut idx, mut prefix, mut suffix, mut mul) = (0, 0, 0, 1);
        for (i, c) in s.chars().enumerate() {
            let t = c as u64 - '0' as u64 + 1;
            prefix = prefix * base + t;
            suffix = suffix + t * mul;
            mul *= base;
            if prefix == suffix {
                idx = i + 1;
            }
        }
        if idx == s.len() {
            s
        } else {
            let x: String = (&s[idx..]).chars().rev().collect();
            String::from(x + &s)
        }
    }
}

214 - Shortest Palindrome

Question

Algorithm

Examples:

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Examples:

Code

All Problems

All Solutions