LeetCode：3.无重复字符的最长子串

标签：子串 字符 oneNeedle -- longestStr length let str LeetCode

LeetCode：3.无重复字符的最长子串

优化用kmp

解题步骤用双指针维护一个滑动窗囗，用来剪切子串。不断移动右指针，遇到重复字符，就把左指针移动到重复字符的下一位。过程中，记录所有窗口的长度，并返回最大值。

时间复杂度：O(n)空间复杂度：O(m)，m是字符串中不重复字符的个数

var lengthOfLongestSubstring = function(s) {
    let str = '';
    let longestStr = '';
    for (let i = 0; i < s.length; i++) {
        if (!str.includes(s[i])) {
            str += s[i];
        } else {
            // Check if the current substring is longer than the longest found so far
            if (str.length > longestStr.length) {
                longestStr = str;
            }
            // Find the position of the repeated character in the current substring
            const repeatIndex = str.indexOf(s[i]);
            // Start a new substring from the next character after the repeated one
            str = str.substring(repeatIndex + 1) + s[i];
        }
    }
    // Final check to update the longest substring if needed
    if (str.length > longestStr.length) {
        longestStr = str;
    }
    console.log(longestStr);
    return longestStr.length;
};
console.log(lengthOfLongestSubstring('pwfwkew'))
//只能用 string 和数组  time O(n*n)  space O(n)

//Map Solution time O(n)  space O(m)
var lengthOfLongestSubstring = function(s) {
    let oneNeedle=0
    let twoNeedle=0
    let map=new Map()
    for(let i=0;i<s.length;i++){
        if(map.has(s[i])&&map.get(s[i])>=oneNeedle){
            oneNeedle=map.get(s[i])+1
        }
        twoNeedle=Math.max(twoNeedle,i-oneNeedle+1)
        map.set(s[i],i)
    }
    return twoNeedle
};
console.log(lengthOfLongestSubstring('pwfwkew'))

flowchart TD A[开始] --> B{是否遍历结束} B -->|No| C[获取当前字符] C --> D{字符是否存在于 map 且位置 >= oneNeedle} D -->|Yes| E[更新 oneNeedle] D -->|No| F[跳过更新 oneNeedle] E --> G[更新最大长度] F --> G G --> H[更新 map] H --> B B -->|Yes| I[返回最大长度]

'

标签：子串,字符,oneNeedle,--,longestStr,length,let,str,LeetCode
From： https://www.cnblogs.com/KooTeam/p/18665872