2023年10月28日

Leetcode-无重复字符最长字串

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

**示例 1:**输入: s = “abcabcbb” 输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

**示例 2:**输入: s = “bbbbb” 输出: 1 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

**示例 3:**输入: s = “pwwkew” 输出: 3 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。   请注意，你的答案必须是 子串 的长度，"pwke" 是一个_子序列，_不是子串。

提示：

  • 0 <= s.length <= 5 * 104

  • s 由英文字母、数字、符号和空格组成

class Solution {
public:
    bool has_no_repeat_char(std::string &str)
    {
        for (auto &s : str)
        {
            if (std::count(str.begin(), str.end(), s) > 1)
                return false;
        }
        return true;
    }
    int lengthOfLongestSubstring(string s) {
        if (s.size() == 0 || s.size() == 1)
            return static_cast<int>(s.size());
        int max_length = 0;
        int left = 0;
        std::unordered_map<char, int> map;
        for (auto right = 0; right < s.size(); ++right)
        {
            auto cr = s[right];
            if (map.find(cr) != map.end() && map[cr] >= left)
            {
                // 前面已存在
                left = map[cr] + 1;
            }
            map[cr] = right;
            max_length = std::max(max_length, right - left + 1);
        }
        return max_length;
    }
};

  1. 定义两个指针left和right，分别表示无重复字符子串的左右边界。

  2. 初始化最大长度max_length为0，以及一个哈希表charMap用于记录字符出现的位置。

  3. 遍历字符串，不断移动右指针right：

    • 如果当前字符s[right]已经在charMap中出现过，并且上次出现的位置在当前无重复字符子串的范围内（即大于等于left），则更新左指针left为上次出现位置的下一个位置。

    • 更新字符s[right]在charMap中的位置为right。

    • 计算当前无重复字符子串的长度cur_length = right - left + 1。

    • 更新最大长度max_length为max(max_length, cur_length)。

  4. 返回最大长度max_length。