试题链接:61. 最长不含重复字符的子字符串 - AcWing题库
- 思路:使用滑动窗口算法,维护窗口中的字符不重复,滑动时记录窗口的最大值即可,由于只包含小写字符,可以用一个 32 位整形的二进制形式表示。
- 时间复杂度:O(n)
- 空间复杂度:O(1)
class Solution {
public:
int longestSubstringWithoutDuplication(string s) {
int bitmap = 0;
int ans = 0, cnt = 0;
int l = 0, r = 0, n = s.size();
while (r < n) {
while (l < r && ((bitmap >> (s[r] - 'a')) & 1)) {
bitmap ^= 1 << (s[l] - 'a');
l++;
}
bitmap |= 1 << (s[r] - 'a');
ans = max(ans, r - l + 1);
r++;
}
return ans;
}
};