题目描述

题目链接：3. Longest Substring Without Repeating Characters

Given a string s, find the length of the longest substring without repeating characters.

例子

例子 1

Input: s = “abcabcbb” Output: 3 Explanation: The answer is “abc”, with the length of 3.

例子 2

Input: s = “bbbbb” Output: 1 Explanation: The answer is “b”, with the length of 1.

例子 3

Input: s = “pwwkew” Output: 3 Explanation: The answer is “wke”, with the length of 3. Notice that the answer must be a substring, “pwke” is a subsequence and not a substring.

例子 4

Input: s = "" Output: 0

Constraints

• 0 <= s.length <= 5 * 10^4
• s consists of English letters, digits, symbols and spaces.

解题思路

这道题关键是判断一个字符串中的子串是否包含重复字符，这一目标可以用哈希表来实现。我们通过维护一个滑动窗口，并用一个哈希表记录该窗口中出现过字符。窗口右侧持续扩张并将新出现的字符添加进哈希表中，如果发现有重复字符时，收缩左侧并持续将该位置字符从哈希表中删除直到到新出现的字符位置处。扩张过程中实时维护最长不重复子串的长度，最后返回即可。

代码如下：

#include <string>
#include <vector>
#include <climits>

class Solution {
public:
    int lengthOfLongestSubstring(std::string s) {
        std::vector<int> record(256, -1);
        int len = 0;
        int front = 0, back = 0;
        
        while (back < s.length()) {
            int ind = static_cast<int>(s[back]);
            if (record[ind] == -1) {
                record[ind] = back;
                len = std::max(len, back - front + 1);
            } else {    // found repeat characters
                while (front != record[ind]) {
                    record[s[front]] = -1;
                    front++;
                }
                front++;
                record[ind] = back;
            }
            back++;
        }

        return len;
    }
};

• 时间复杂度: O(n)
• 空间复杂度: O(1) - 字符数量为常数256

GitHub 代码同步地址： 3.LongestSubstringWithoutRepeatingCharacters.cpp

其他题目： GitHub: Leetcode-C++-Solution 博客: Leetcode-Solutions