Leetcode | Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.

采用和Minimum Window Substring类似的思路。这里用一个pos[256]来存储每个字符出现的位置。每次求以i为结束的最长长度。

如果当前字符出现过，那么长度就是上次出现pos[s[i]]到当前位置i的长度；

如果没出现过，那么长度++。

 1 class Solution {
 2 public:
 3     int lengthOfLongestSubstring(string s) {
 4         int pos[256];
 5         memset(pos, -1, 256 * sizeof(int));
 6         int len = 0, max = 0;
 7         for (int i = 0; i < s.length(); ++i) {
 8             if (pos[s[i]] >= 0) {
 9                 for (int j = i - len; j < pos[s[i]]; ++j) pos[s[j]] = -1;
10                 len = i - pos[s[i]];
11             } else {
12                 len++;
13             }
14             pos[s[i]] = i;
15             if (len > max) max = len;
16         }
17         
18         return max;
19     }
20 };

注意这里内循环(Line 9)中j是一直递增的，且这个范围是不会重复计算的。所以最坏情况下，内循环的总开销是O(n)，整个算法最坏情况是O(2*n)。

第三次写，思路是统计到当前位置满足条件的串长度。每次找起始和终点。

 1 class Solution {
 2 public:
 3     int lengthOfLongestSubstring(string s) {
 4         if (s.empty()) return 0;
 5         int start = 0, n = s.length(), next = 0, max = 1;
 6         unordered_map<char, int> freqs;
 7         
 8         while (start < n) {
 9             for (; next < n && (freqs.count(s[next]) <= 0 || freqs[s[next]] == 0); next++) freqs[s[next]]++;  
10             if (next - start > max) max = next - start;
11             if (next == n) break;
12             for (; start < next && s[start] != s[next]; start++) freqs[s[start]] = 0;
13             freqs[s[start++]] = 0;
14         }
15         
16         return max;
17     }
18 };