1. 题目
  2. 解题思路
  3. 优化

3 Longest Substring Without Repeating Characters

leetcode algorithm

题目

Given a string, find the length of the longest substring without repeating characters.

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Example 1:
Input: "abcabcbb"
Output: 3 
Explanation: The answer is "abc", with the length of 3. 

Example 2:
Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:
Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3. 
Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

解题思路

遍历字符,用一个变量(a)记录遍历过的不重复子串.
如果遇到了重复的字符,则比较a的长度,判断是否比之前的长.然后移除a开头到重复的部分的字符.

时间复杂度 O(n^2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
const lengthOfLongestSubstring = (s) => {
    let i = 0;
    let maxLen = 0;
    let tempStr = '';
    while (i < s.length) {
        const letter = s[i];
        const lastSameI = tempStr.indexOf(letter)
        if (lastSameI >= 0) {
            const tempStrLen = tempStr.length;
            if ( tempStrLen > maxLen) {
                maxLen = tempStrLen;
            }
            tempStr = tempStr.slice(lastSameI + 1);
        } 
        tempStr += letter;
        i += 1;
    }
    const tempStrLen = tempStr.length;
    if ( tempStrLen > maxLen) {
        maxLen = tempStrLen;
    }
    return maxLen;
};

测试

1
2
3
4
5
6
7
8
9
// test
console.log(lengthOfLongestSubstring("abc") === 3);
console.log(lengthOfLongestSubstring("bbbb") === 1);
console.log(lengthOfLongestSubstring("wkew") === 3);
console.log(lengthOfLongestSubstring("cabcbb") === 3);
console.log(lengthOfLongestSubstring("dvdf") === 3);
console.log(lengthOfLongestSubstring("tmmzuxt") === 5);
console.log(lengthOfLongestSubstring("gububgvfk") === 6);
console.log(lengthOfLongestSubstring(" ") === 1);

优化

用哈希表实现.
遍历字符串,记录当前不重复子串的起始坐标.
根据上一个相同字符和子串起始坐标的相对位置来判断是否重复.

时间复杂度 O(n)

Object实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
const lengthOfLongestSubstring = (s) => {
    let i = 0;
    let maxLen = 0;
    let left = 0; // 当前子串的左侧位置
    const map = {};
    while (i < s.length) {
        const letter = s[i];
        const repeat = map[letter];
        if (repeat >= 0 && repeat >= left) {
            if (i - left >= maxLen) {
                maxLen = i - left;
            }
            // 有重复, 重置左侧位置
            left = repeat + 1
        }
        map[letter] = i
        i += 1;
    }
    // 最后一位为不重复子串, 且当前的不重复子串 > maxLen
    if (s.length - left > maxLen) {
        maxLen = s.length - left;
    }
    return maxLen;
};

Map实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
const lengthOfLongestSubstring = (s) => {
    let i = 0;
    let maxLen = 0;
    let left = 0; 
    const map = new Map();
    while (i < s.length) {
        const letter = s[i];
        const repeat = map.get(letter);
        if (repeat >= 0 && repeat >= left) {
            if (i - left >= maxLen) {
                maxLen = i - left;
            }
            left = repeat + 1
        }
        map.set(letter, i);
        i += 1;
    }
    if (s.length - left > maxLen) {
        maxLen = s.length - left;
    }
    return maxLen;
};