Leetcode最长回文子串问题

Question

LeetCode第五题，最长回文子串问题，其中Python下面有一种解法，原理有点看不懂，英文描述如下：

Basic thought is simple. when you increase s by 1 character, you could only increase maxPalindromeLen by 1 or 2, and that new maxPalindrome includes this new character. Proof: if on adding 1 character, maxPalindromeLen increased by 3 or more, say the new maxPalindromeLen is Q, and the old maxPalindromeLen is P, and Q>=P+3. Then it would mean, even without this new character, there would be a palindromic substring ending in the last character, whose length is at least Q-2. Since Q-2 would be >P, this contradicts the condition that P is the maxPalindromeLen without the additional character.

So, it becomes simple, you only need to scan from beginning to the end, adding one character at a time, keeping track of maxPalindromeLen, and for each added character, you check if the substrings ending with this new character, with length P+1 or P+2, are palindromes, and update accordingly.

下面是代码：

class Solution:
    # @return a string
    def longestPalindrome(self, s):
        if len(s)==0:
            return 0
        maxLen=1
        start=0
        for i in xrange(len(s)):
            if i-maxLen >=1 and s[i-maxLen-1:i+1]==s[i-maxLen-1:i+1][::-1]:
                start=i-maxLen-1
                maxLen+=2
                continue

            if i-maxLen >=0 and s[i-maxLen:i+1]==s[i-maxLen:i+1][::-1]:
                start=i-maxLen
                maxLen+=1
        return s[start:start+maxLen]

我主要是不明白他的反证法，特别是这个

Then it would mean, even without this new character, there would be a palindromic substring ending in the last character, whose length is at least Q-2.

这里非常困惑，为什么没有这个新字符，它会有以，前一个字符结尾的最长子串，还有为什么是Q-2？恳请大神可以解答疑惑

Answer 1

这段英文不难理解, 翻译一下就是

基本思想很简单。当你将s增加1个字符时，你只能将maxPalindromeLen增加1或2，并且新的maxPalindrome包含这个新字符。证明：如果在添加1个字符时，maxPalindromeLen增加3或更多，则表示新的maxPalindromeLen为Q，旧的maxPalindromeLen为P，Q> = P + 3。那么这就意味着，即使没有这个新字符，也会有一个以最后一个字符结尾的回文子串，其长度至少为Q-2。由于Q-2将> P，这与P是没有附加字符的maxPalindromeLen的条件相矛盾。
因此，这变得简单，您只需要从头到尾扫描，一次添加一个字符，跟踪maxPalindromeLen，并为每个添加的字符，检查以这个新字符结尾的子字符串，长度为P + 1或P + 2，是回文，并相应更新。

举个例子:

a = Solution()

print(a.longestPalindrome('aababbaba'))
print(a.longestPalindrome('abcb'))
print(a.longestPalindrome('abcbc'))
print(a.longestPalindrome('abcbcba'))

输出

ababbaba
bcb
bcb
abcbcba

所谓回文, 即得出的子串相对中心字符左右对称