[LeetCode] [0003] Longest Substring Without Repeating Characters
描述
Given a string, find the length of the longest substring without repeating characters.
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.
分析
假设在第 j-1
轮,已经找到了长度为 j-i
的不重复字串,接下来判断 j
是否在下标 i
到 j-1
中存在相同的字符,若不存在,则更新不重复长度为 j-i+1
;若存在重复,则设置 i=k+1
并更新不重复子串长度为 j-k
。在下一轮判断 j+1
是否重复时,只需从 k+1
遍历到 j
即可。遍历字符串的复杂度为 $$\mathcal{O}(n)$$,遍历子串的复杂度为 $$\mathcal{O}(m)$$,因此整体的时间复杂度为 $$\mathcal{O}(n^2)$$,空间复杂度为 $$\mathcal{O}(1)$$。
int lengthOfLongestSubstring(char* s) {
int longest = 1, sublong = 1;
int i = 0, j = 0;
if (!s[0])
return 0;
while(s[++j]) {
for (int k = i; k < j; k++) {
if (s[j] == s[k]) {
longest = longest > sublong ? longest : sublong;
i = k + 1;
sublong = j - i;
break;
}
}
sublong++;
}
longest = longest > sublong ? longest : sublong;
return longest;
}
结果
Runtime: 12 ms, faster than 89.94% of C online submissions for Longest Substring Without Repeating Characters.
Memory Usage: 12.5 MB, less than 83.11% of C online submissions for Longest Substring Without Repeating Characters.
优化
我们在第一种方法的基础上,通过牺牲空间换取时间的方式,建立一张映射表,映射表的键为字符,值为该字符上一次出现的位置,则可以将时间复杂度降到 $$\mathcal{O}(n)$$,已知字符的数量有限(256个),因此建立映射表的空间开销是固定的,所以空间复杂度为 $$\mathcal{O}(1)$$。
int lengthOfLongestSubstring(char* s) {
int x[256] = { -1 }; // can not set to -1 on some compiler
for (int i=0; i<256; i++) x[i] = -1;
int longest = 0, pos = -1, i = -1;
while(s[++i]) {
pos = x[s[i]] > pos ? x[s[i]] : pos;
x[s[i]] = i;
longest = longest < (i-pos) ? i-pos : longest;
}
return longest;
}
结果
Runtime: 12 ms, faster than 89.94% of C online submissions for Longest Substring Without Repeating Characters.
Memory Usage: 12.4 MB, less than 96.62% of C online submissions for Longest Substring Without Repeating Characters.
本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可。