Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

  1. 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.
  2. 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