# My 7-lines recursive Java solution

• The idea is to use two anchors `j` and `i` to compare the String from beginning and end.
If `j` can reach the end, the String itself is Palindrome. Otherwise, we divide the String by `j`, and get `mid = s.substring(0, j)` and `suffix`.

We reverse `suffix` as beginning of result and recursively call `shortestPalindrome` to get result of `mid` then appedn `suffix` to get result.

``````    int j = 0;
for (int i = s.length() - 1; i >= 0; i--) {
if (s.charAt(i) == s.charAt(j)) { j += 1; }
}
if (j == s.length()) { return s; }
String suffix = s.substring(j);
return new StringBuffer(suffix).reverse().toString() + shortestPalindrome(s.substring(0, j)) + suffix;``````

• This is an elegant solution, can you explain more about why this algorithm will produce the shortest palindrome? And what will be the time complexity? Thanks.

• Very clean and good answer.
Anyone knows how to explain this solution?

• I'm not sure the time complexity. I think it's `O(nlog(n))` but I don't know how to prove it.

• This is `O(n)` algorithm IMO. In the two extreme cases where s itself is a palindrome and where you have to copy the entire string and reverse it to make a palindrome, it's both `O(n)`. Very good answer. ps: You could use StringBuilder instead of StringBuffer, it reflects a much shorter running time.

• I'm not sure it's `O(n)`. How can prove two extreme cases is the worst case?

• Brilliant solution. While not a proof, out of curiosity I decided to count how many recursive calls are needed to pass all tests, and the answer is 2. So function is called 3 times total at most.
I think the upper bound of complexity is O(N(lg(26))) which is O(N)

• I wanna construct a worst case, that may need more than 2 times recursive calls. But I can't find a good model to construct that.

I mean the tests may not cover all worst cases.

• This post is deleted!

• I did bunch of expriments and worst performance is achieved having just 2 distinct characters in a string randomy distributed. (The ratio of characters doesn't have to be the same) Turns out that worst case performance is 2N. While number of calls is logarithmic, due to size reduction on each call total operations converges to linear value.
Here are test results of shuffled array of 'a' and 'b' of size 2M

``````Length of String: 2000000. Total of all lengths: 2000000
Length of String: 1000503. Total of all lengths: 3000503
Length of String: 500559. Total of all lengths: 3501062
Length of String: 250657. Total of all lengths: 3751719
Length of String: 125204. Total of all lengths: 3876923
Length of String: 62644. Total of all lengths: 3939567
Length of String: 31254. Total of all lengths: 3970821
Length of String: 15495. Total of all lengths: 3986316
Length of String: 7691. Total of all lengths: 3994007
Length of String: 3822. Total of all lengths: 3997829
Length of String: 1919. Total of all lengths: 3999748
Length of String: 961. Total of all lengths: 4000709
Length of String: 496. Total of all lengths: 4001205
Length of String: 240. Total of all lengths: 4001445
Length of String: 114. Total of all lengths: 4001559
Length of String: 64. Total of all lengths: 4001623
Length of String: 36. Total of all lengths: 4001659
Length of String: 24. Total of all lengths: 4001683
Length of String: 15. Total of all lengths: 4001698
Length of String: 8. Total of all lengths: 4001706
Length of String: 5. Total of all lengths: 4001711
Length of String: 2. Total of all lengths: 4001713
``````

• Hi I try to explain the elegant solution of @xcv58. At first I clarify some notation: in the following paragraph mid point of a palindrome `"abcdcba"` denotes `'d'`; when I say `charAt(1)=='b'` pairs with `charAt(5)=='b',` I mean they are at symmetric positions.

Take `"gxybakbkabbfmbnnnjjjyxqg"` as example. After for loop j stops at `j'==10` where `charAt(10)=='b'`. Then it reaches such a status: To make the final result be a valid palindrome, in the final result this `'b'` at index `j'` neither could be the mid point nor could pair with any other `'b'` in the string `s`.

Now we prove this by contradiction, in 1st case if `charAt(j')` is the mid point, then `substring(0,2*j'+1)` should be palindrome (otherwise the final result was not palindrome), and when `substring(0,2*j'+1)` is palindrome, using our for loop mentioned before, `j` would stops with index at least `2*j'+1`, which is a contradiction. Similarly in 2nd case if `charAt(j')` could pair with some `charAt(i)` in the final result, then `substring(0,j'+i+1)` should be palindrome, if `j'+i+1` is already > `s.length()`, it's a contradiction(we can't add characters at backside); else when substring`(0,j'+i+1)` is palindrome, `j` would stops with index at least `j'+i+1`, which is a contradiction.

Then we have the conclusion: to pair the `charAt(j)=='b'` in the final result, we must add `new char 'b'` from the front of `s`, and since they are paired, all chars on the right side of `j` should be paired by some newly added chars => We MUST add `substring(j)'s` reverse string in front of `s` => This is the shortest way to transform `s` to palindrome. Later we deal with `substring(0,j)` recursively.

• Cool, I'm too lazy to do this.

But still we don't have a formal proof for time complexity.

• Hi @qianzhige, for the reason it's shortest palindrome, you could see my explanation below :)

• Thanks for your comment. Maybe later we would try to find a proof for time complexity. Now it's 2am and I'm too sleepy :)

• Of course, take it easy.

• This post is deleted!

• Hi, I think I can't prove the linear time complexity. Since I construct a test case that "abacfghcabakmnchgfcabaiuytrcfghcnmkabachgfcaba" in which we need to call the function for 5 times.

• "abacfghcabakmnchgfcabaiuytrcfghcnmkabachgfcaba" This is a test case which need 5 calls...

• Brilliant code and brilliant test case. I agree that the algorithm is O(nlogn).

• This post is deleted!

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