The longest anagram substring

This is the 22nd day of my participation in the Gwen Challenge in November.

The title

Given a string s, find the longest substring in s. Example 1:

Input: s = “babad” Output: “bab” Explanation: “ABA” is also the answer to the question. Example 2:

Input: s = “CBBD” Output: “bb” Example 3:

Input: s = “a” Output: “a” Example 4:

Input: s = “ac” Output: “A” Hint: 1 <= S. length <= 1000 s Consists of only digits and English letters (uppercase and/or lowercase)

Train of thought

Central diffusion method how to retrieve text string? Start at each position and spread out to both sides. Meet not palindrome when the end. For example, STR = ACdbbdaastr =acdbbdaa we need to find what is the longest palindrome string from the first b (position 33). How? First look left for the same character as the current position until you encounter an inequality. Then go to the right to find the same character as the current position until unequal is encountered. Finally, left and right diffuse in both directions until left and right are not equal. As shown below:

One window size (len) appears for each location spread out to the sides. If len>maxLen(used to indicate the length of the longest palindrome string). Then update the value of maxLen. Because we’re going to return a concrete substring, not a length, we also need to record the starting position (maxStart) at maxLen, that is, maxStart=len.

code

Start at each position and spread out to both sides. Meet not palindrome when the end. For example, STR = ACdbbdaastr =acdbbdaa we need to find what is the longest palindrome string from the first b (position 33). How? First look left for the same character as the current position until you encounter an inequality. Then go to the right to find the same character as the current position until unequal is encountered.

    console.log(s.length)
    if (s == null || s.length == 0) {
            return "";
        }
    let strLen = s.length;
    let left = 0;
    let len = 1
    let right = 0;
    let maxLen = 0;
    let maxStart = 0;
    for(let i = 0; i < strLen; i++) {
        left = i - 1;
        right = i + 1;
        while(s[left] === s[i] && left >= 0) {
            len++;
            left--
        }
        while(s[right] === s[i] && right< strLen) {
            len++;
            right++
        }
        while(left >= 0 && right < strLen && s[left] === s[right]) {
            len = len + 2;
            left--;
            right++
        }
        console.log(len)
        if (len > maxLen) {
                maxLen = len;
                maxStart = left;
            }
            len = 1;
    }
    return s.substring(maxStart + 1, maxStart + maxLen + 1);

};
Copy the code