0%

LeetCode 3. Longest Substring Without Repeating Characters

Posted on Edited on In

题目

原题在此
Given a string s, find the length of the longest substring without repeating characters.

Example 1:
Input: s = “abcabcbb”
Output: 3
Explanation: The answer is “abc”, with the length of 3.

Example 2:
Input: s = “bbbbb”
Output: 1
Explanation: The answer is “b”, with the length of 1.

Example 3:
Input: s = “pwwkew”
Output: 3
Explanation: The answer is “wke”, with the length of 3.
Notice that the answer must be a substring, “pwke” is a subsequence and not a substring.

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

Constraints:

  • 0 <= s.length <= 5 * 104
  • s consists of English letters, digits, symbols and spaces.

解析

用map<char, int>储存每个字符最后出现的index。采用”滑动窗口”法, 指向子串尾端的指针持续扫描整个字符串,在遇到重复时将更新首指针指向重复字符的下一个。记录（更新）每个字符最后出现的index。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        vector<int> m(256, -1);
        int res = 0, idx = -1;
        for(int i = 0; i < s.size(); ++i){
            if(m[s[i]] > idx) idx = m[s[i]];
            m[s[i]] = i;
            res = max(res, i - idx);
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func lengthOfLongestSubstring(s string) int {
    
    m := make(map[rune]int)
    var res, idx = -1, 0
    for i,r := range s{
        if m[r] > idx {
            idx = m[r]
        }
        m[r] = i
        if(i - idx > res) {
            res = i - idx
        }
        m[r]++;
    }
    return res + 1
}