# Shortest Palindrome

• #3 Implementation may not be able to handle the case if '#' is in string s.
Here is an implementation to remove the limitation.

```        string rev(s.rbegin(), s.rend());
if (s == rev)
return s;
vector<int> lps(rev.size(), 0);
int len = 0;
for (int i = 1; i < rev.size(); i++) {
while (len > 0 && rev[i] != s[len])
len = lps[len - 1];
if (rev[i] == s[len])
len++;
lps[i] = len;
}
return rev + s.substr(len, s.size() - len);
```

• @JianMa Thank you for your suggestion. We tried to keep the implementation similar to the original KMP routine for easier understanding. But would surely incorporate the solution as an improvement :)

• For Solution #2, why the time cost is O(NlogN) rather than o(N) when the article claims that the size of string is reduced by half each recursion?
Let T(N) indicates the time complexity of the algorithm in regard of a string of length N. T(N) = T(N/2) +O(N). By replacement, we have T(N) = O(N) + O(N/2) + O(N/4) + ... + O(1) <= O(2N) = O(N). So I think T(N) = O(N) for Solution #2.

• @MITCHELLHE Thanks for the rectification. You are right, the time complexity has been calculated incorrectly and will be updated.

• For solution #2, the worst timing complexity is O(n^2), although in each iteration the string is divided into 2 part, is possible the s[i:] part has very few letters or even only 1 letter. Thus T(N) = T(N-1) + O(N) --> O(n^2)
e.g. s = "aababababababababababa"
@MITCHELLHE @abhinavbansal0

• @CONOVER yes you are right. Extremely sorry to have missed this case. Thank you for the correction :)

• The algorithm to generate lookup table can be improved. There is no need to assign t = f(i-1) during each iteration. t is simply pointing to the first letter outside the longest prefix. Therefore, the whole idea to do f[i] = ++t is to both assign f[i] with the right value and move t to the right position for next iteration.
f(0) = 0
for(i = 1; i < n; i++)
{
while(t > 0 && b[i] != b[t])
t = f(t-1)
if(b[i] == b[t]){
f(i) = ++t;
}

Should do the work.

• For no.1 (brute force), iterating over every character in the string is O(n), but every substring comparison is O(1) in Java. So the total time complexity should be O(n) in Java

• Comparing substrings in Java cannot be done in O(1). As a proof, if it could, it would be possible to compare whole strings in O(1) by simply splitting them up after the first character and comparing the substrings you are left with.

• I did this in javascript and I keep timing out even though my solution is O(n). I don't think its even possible to do.

• tried both the first and the second methods in Python, all time limit error.

• @meame2010 said in Shortest Palindrome:

tried both the first and the second methods in Python, all time limit error.

I just tried that as well and got both accepted fine.

• smart approach 3 using KMP. One possible improvement I feel is that we might not need to build s+"#"+reverse(s) . To find longest prefix in s that matches the suffix in its reverse, like you mentioned, we keep moving s to the right and compare it to its reserve. This is very similar to general string match with one difference that when pointer in reserve string reaches end, the pointer in s is the position we look for.

So sessionally what we need is implementing KMP string match plus this logic. And of course, implementation includes building a prefix lookup table for s to speed up the matching process.

• To achieve O(n) complexity you could use hashing instead of KMP to look for the greatest border of the string T = S + '#' + reverse(S). You keep two pointers L and R, and loop over i:
for(i=0; T[i] != '#'; i++){
prefixHash = (prefixHash + T[i]prime^i) % mod
suffixHash = (suffixHash
prime^i + T[i]) % mod
if(prefixHash == suffixHash) border found!
}

• @fiorifj sorry, there were some mistakes

To achieve O(n) complexity you could use hashing instead of KMP to look for the greatest border of the string T = S + '#' + reverse(S). You loop over i:

last = T.length()-1
for(i=0; T[i] != '#'; i++){
prefixHash = (prefixHash + T[i]prime^i) % mod
suffixHash = (suffixHash
prime + T[last-i]) % mod
if(prefixHash == suffixHash) border found!
}

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.