🧩 Problem Statement
Given a string s, you can convert it to a palindrome by adding characters in front of it.
Return the shortest palindrome you can find by performing this transformation.
📘 Example
go
Input: s = "aacecaaa"
Output: "aaacecaaa"
Input: s = "abcd"
Output: "dcbabcd"
🧠 Approach
To create the shortest palindrome by adding characters in front, we want to find the longest prefix of s which is a palindrome. Then reverse the remaining suffix and add it in front.
We'll use the KMP failure table (partial match table) to efficiently find this longest palindromic prefix.
📌 Steps:
- Build a new string:
s + "#" + reverse(s)
- Build the KMP prefix table for this combined string.
- The value at the end of the table tells us how many characters at the start of
s match the end of reverse(s).
- Reverse the unmatched suffix and prepend it to
s.
✅ Go Implementation
go
package main
import (
"fmt"
)
func shortestPalindrome(s string) string {
rev := reverse(s)
combined := s + "#" + rev
lps := buildLPS(combined)
toAdd := rev[:len(s)-lps[len(lps)-1]]
return toAdd + s
}
func buildLPS(pattern string) []int {
n := len(pattern)
lps := make([]int, n)
length := 0
for i := 1; i < n; i++ {
for length > 0 && pattern[i] != pattern[length] {
length = lps[length-1]
}
if pattern[i] == pattern[length] {
length++
lps[i] = length
}
}
return lps
}
func reverse(s string) string {
r := []rune(s)
for i, j := 0, len(r)-1; i < j; i, j = i+1, j-1 {
r[i], r[j] = r[j], r[i]
}
return string(r)
}
📦 Example Usage
go
func main() {
fmt.Println(shortestPalindrome("aacecaaa")) // Output: "aaacecaaa"
fmt.Println(shortestPalindrome("abcd")) // Output: "dcbabcd"
}
⏱️ Time & Space Complexity
- Time Complexity: O(n), where
n is the length of the string
- Space Complexity: O(n), for the LPS array and temporary strings
💡 Key Concepts
- Using KMP algorithm for efficient prefix/suffix matching.
- Reversing the suffix and prepending = minimal additions.
- Trick:
s + "#" + reverse(s) ensures safe delimiter and alignment check.