Question 4: Longest callback substring

Given a string s, find the longest echo substring in S.

Example 1:

Input: s = "babad" Output: "bab" Explanation: "aba" is also a correct answer.Copy the code

Example 2:

Input: s = "CBBD" Output: "bb"Copy the code

Example 3:

Input: s = "a" Output: "a"Copy the code

Example 4:

Input: s = "ac" Output: "a"Copy the code

Tip:

1 <= s.length <= 1000 s Consists of only numbers and letters (upper and/or lower case)Copy the code

答 案 :

  1. Handle the boundary case, and return the original string if the character length is less than 2

  2. Define two variables: start stores the start position of the maximum palindrome string currently found, and maxLength records the length of the string (the end position is start+ maxLength).

  3. Create a help function that determines if the left and right are out of bounds and if the leftmost character is equal to the rightmost character. If all three conditions are met, then determine if you need to update the maximum length and the starting position of the maximum string, then left–, right++, continue to determine, Until one of the three conditions is not met.

  4. Walk through the string, calling the Help function twice at each position, first checking I -1, I +1, and second checking I, I +1

    Why double check?

    1. For the first time, use I as the center to see if it can form the maximum back text substring

    2. The second time is to assume that there is no center, to see if there is a maximum back substring

Illustration:

Code:

/** * @param {string} s * @return {string} */ var longestPalindrome = function (s) { if (s.length < 2) { return s; } let start = 0; let maxLength = 1; function expandAroundCenter(left, right) { while (left >= 0 && right < s.length && s[left] === s[right]) { if (right - left + 1 > maxLength) { maxLength =  right - left + 1; start = left; } left--; right++; } } for (let i = 0; i < s.length; i++) { expandAroundCenter(i - 1, i + 1); expandAroundCenter(i, i + 1); } return s.substring(start, start + maxLength); };Copy the code

Additional knowledge:

The length of a,b,c:

Index number 0,1,2; Algorithm: 2-0 + 1