leetcode3：无重复字符的最长子串

题目链接

leetcode

题目描述

给定一个字符串 s ，找出其中不含有重复字符的最长子串的长度。

C++ 代码

#include <iostream>
#include <string>
#include <unordered_set>
#include <unordered_map>
#include <vector>
using namespace std;

/*
    暴力解法

    枚举字符串中所有可能的子串，检查每个子串是否包含重复字符。
    如果无重复，则记录它的长度，并更新最大值。

    时间复杂度：O(n^2)
    空间复杂度：O(min(m, n))
        m 是字符集大小（ASCII 码 128 个字符），n 是字符串长度。
*/
class Solution_0 {
public:
    int lengthOfLongestSubstring(string s) {
        int n = s.size();
        int res = 0;

        for (int i = 0; i < n; i++) {
            unordered_set<char> visited;
            for (int j = i; j < n; j++) {
                if (visited.count(s[j])) {
                    break; // 出现重复字符，结束这次循环
                }
                visited.insert(s[j]);
                res = max(res, j-i+1);
            }
        }

        return res;
    }
};

/*
    两个指针 i,j 表示当前遍历的子串是 s[i,j]。
    维护一个哈希表，统计 s[i,j] 中每个字符出现的次数。

	这题比其他滑动窗口的题目简单，need 和 valid 都不需要，
	更新窗口内数据只需要简单的更新计数器 window 即可。
	当 window[c] 大于 1 时，说明窗口中存在重复字符，移动 left 缩小窗口。
   	另外，在收缩窗口完成后更新 res。
    因为窗口收缩的 while 条件是存在重复元素，所以收缩完成后窗口中没有重复元素。

    时间复杂度：O(n)
        其中 n 是字符串的长度。
        左指针和右指针分别遍历整个字符串一次。
    空间复杂度：O(min(m, n))
        m 是字符集大小（ASCII 码 128 个字符），n 是字符串长度。
*/
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char, int> window;
        int res = 0;
        
        for (int left = 0, right = 0; right < s.size(); right++) {
            char c = s[right];
            window[c]++;

            // 判断左侧窗口是否需要收缩
            while (window[c] > 1) {
                window[s[left]]--;
                left++;
            }
            
            // 更新答案
            res = max(res, right - left + 1);
        }

        return res;
    }
};

int main() {
    Solution solution;
    vector<string> s_cases = { 
        "abcabcbb", 
        "bbbbb", 
        "pwwkew"
    };

    for (auto &t : s_cases) {
        cout << "Input: s = \"" << t << "\"" << endl;
        cout << "Output: " << solution.lengthOfLongestSubstring(t) << endl;
    }

    return 0;
}