Longest Substring Without Repeating

Posted by Bill on March 11, 2023

Longest Substring Without Repeating Characters

Given a string s, 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
16
17
18
19
20
21
22
23
24
25
26
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.

C++ Solution

该问题用暴力方式去解的话,提交会提示超时,所以需要使用些技巧。以abcabcbb这个字符串为例,检测不重复字符可以使用set数据结构 解决,可以观察得出,以第一个字符a为起点,其最长不重复字符串到第三个字符c,而以第二个字符b为起点,最长的字符串到第四个字符。 其规律在于不同的起始点,随着起始字符的右移,结束字符也会右移,所以可以通过时间复杂度为O(n),空间复杂度为O(ASCII字符集)的方法解决,即滑动窗口方式。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<iostream>
#include<string>
#include<set>
using namespace std;
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
      int left = 0, right = 0;
      int len = s.length();
      int ans = 0;
      set<char> uniqueSet;
      for (left = 0 ; left < len; left++) {
        uniqueSet.clear();
        right = left;
        while (right < len) {
          if (uniqueSet.count(s[right]) == 0) {
            uniqueSet.insert(s[right++]);
            continue;
          }
          else {
            break;
          }
        }
        int currentLen = uniqueSet.size();
        if (currentLen > ans) {
          ans = currentLen;
        }
      }
      return ans;
    }
};

void test(string input, int expect) {
  Solution *solution = new Solution();
  int ans = solution->lengthOfLongestSubstring(input);
  if (ans == expect) {
    cout<<"test passed!"<<endl;
  } else {
    cout<<"test failed!"<<endl;
  }
  delete solution;
}

int main() {
  test(string("abcabcbb"), 3);
  test(string("bbbbb"), 1);
  test(string("pwwkew"), 3);
  test(string(""), 0);
  test(string("a"), 1);
  test(string(" "), 1);
}