Practice › Strings
Shortest Palindrome by Adding in Front
Hard · Strings · Asked at Google, Amazon, Microsoft
You may add characters only at the front of s. Print the minimum number of characters you must add to make it a palindrome.
Input
A single string s of lowercase letters.
Output
The minimum number of characters to add.
Constraints
- 1 ≤ |s| ≤ 10^5
The answer is |s| minus the length of the longest palindromic prefix. Build t = s + "#" + reverse(s); the last value of its prefix function is that length.
Example 1
Input
aacecaaa
Output
1
Example 2
Input
abcd
Output
3
Hints
- If the first L characters of s already form a palindrome, you only need to add the reverse of the remaining |s| − L characters in front.
- The longest palindromic prefix = the longest prefix of s that is also a suffix of reverse(s). The prefix function of s + "#" + reverse(s) gives it directly.
Approach
Let t = s + "#" + reverse(s). The last value of t's prefix function is the length of the longest prefix of s that equals a suffix of reverse(s) — i.e. the longest palindromic prefix (the "#" stops the match from crossing the middle). The answer is |s| − pi.back(). Checking every prefix directly would be O(n²).
Complexity: O(n) time · O(n) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
string s;
cin >> s;
string rev(s.rbegin(), s.rend());
string t = s + "#" + rev;
vector<int> pi(t.size(), 0);
for (size_t i = 1; i < t.size(); i++) {
int k = pi[i - 1];
while (k > 0 && t[i] != t[k]) k = pi[k - 1];
if (t[i] == t[k]) k++;
pi[i] = k;
}
cout << (int)s.size() - pi.back() << "\n";
return 0;
}Python solution
s = input().strip()
t = s + "#" + s[::-1]
pi = [0] * len(t)
for i in range(1, len(t)):
k = pi[i - 1]
while k and t[i] != t[k]:
k = pi[k - 1]
if t[i] == t[k]:
k += 1
pi[i] = k
print(len(s) - pi[-1])Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
String s = new Scanner(System.in).next();
String t = s + "#" + new StringBuilder(s).reverse();
int[] pi = new int[t.length()];
for (int i = 1; i < t.length(); i++) {
int k = pi[i - 1];
while (k > 0 && t.charAt(i) != t.charAt(k)) k = pi[k - 1];
if (t.charAt(i) == t.charAt(k)) k++;
pi[i] = k;
}
System.out.println(s.length() - pi[t.length() - 1]);
}
}Solve Shortest Palindrome by Adding in Front online · All practice problems