leetcode-3-Longest-Substring-Without-Repeating-Characters

发表于   |  

描述

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

Example 1:

1
2
3
Input: "abcabcbb"
Output: 3 
Explanation: The answer is "abc", with the length of 3.

Example 2:

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

Example 3:

1
2
3
4
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.

分析

如果子串里有重复的字符，则父串里也一定有重复字符，因此可以使用贪心法，遍历一次，当遇到重复字符时，将上一个重复字符的 index + 1 作为起始字符，用来计算长度。一直遍历到最后一个字符，时间复杂度是 $O(n)$，空间复杂度是 $O(n)$

解决方案1（python）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        occ = set()
        sLength = len(s)
        right, result = -1, 0
        
        for i in range(sLength):
            if i != 0:
                occ.remove(s[i-1])
            while right+1 < sLength and s[right+1] not in occ:
                occ.add(s[right+1])
                right += 1
            result = max(result, right-i+1)
        return result

解决方案1(Java)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int lengthOfLongestSubstring(String s) {
        int length = s.length(), result = 0;
        int[] index = new int[512];
        int nowStart = 0;
        Arrays.fill(index, -1);
        
        for (int i = 0; i < length; i++) {
            if (index[s.charAt(i)] >= nowStart) {
                result = Math.max(i-nowStart, result);
                nowStart = index[s.charAt(i)] + 1;
            }
            index[s.charAt(i)] = i;
        }
        return Math.max(length-nowStart, result);
    }
}

解决方案2(Golang)

也可以用滑动窗口窗口实现，用一个 map 来记录每个字符是否出现过。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func lengthOfLongestSubstring(s string) int {
    charCountMap := map[byte]int{}
    sLen := len(s)
    right, result := -1, 0
    
    for i := 0; i < sLen; i++ {
        if i != 0 {
            delete(charCountMap, s[i-1])
        }
        for right+1 < sLen && charCountMap[s[right+1]] == 0 {
            charCountMap[s[right+1]]++
            right++
        }
        result = max(result, right-i+1)
    }
    return result
}

func max(x, y int) int {
    if x < y {
        return y
    }
    return x
}

相关问题

题目来源