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.