HOT100 – the longest substring of a loop (JS implementation)

Topic describes

Their thinking

• Methods: Center diffusion method.
• Core: Whether the left and right sides of the target character are equal.
• Two cases are discussed: the case where the length of the substring is odd and the case where the length of the substring is even.
• When you cycle, see if it’s out of bounds, and see if it’s equal.
• See code comments for details.

Freehand thinking (take CBBD string as an example to understand the execution process inside the loop body)

The problem solving code

var longestPalindrome = function(s) {
    // Define the longest callback substring to return
    let res = ' ';
    // Start looping each character
    for (let i = 0; i < s.length; i++) {
        // If the substring is odd
        test(i,i);
        // When the substring is even
        test(i,i+1);
    }
    function test(m,n) {
        // First, the two elements must be equal, then m moves left and n moves right for comparison
        while (m >= 0 && n < s.length && s[m] === s[n]) {
            m--;
            n++;
        }
        // Compares whether the current palindrome string length is longer than the previous palindrome string length, then updates.
        if (n - m - 1 > res.length) {
            res = s.slice(m+1,n); }}return res;
};
Copy the code

Conclusion (this topic gives us the enlightenment of thinking)

• Learn to use the center diffusion method to solve the longest loop substring problem.