3.Longest Substring Without Repeating Characters

Tags: Medium String Two Pointers Sliding Windows Hash Table

Links: https://leetcode.com/problems/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.

---

注意这道题和POJ 3320不同，3320要包含所有知识点，中间可以重复，但是本题中间不可以重复，核心思想仍然是尺取法。

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        int n = s.size();
        unordered_map<char, int> m;
        int start = 0, end = 0;
        int res = 0;
        while (end < n) {
            ++m[s[end]];
            while (m[s[end]] > 1) --m[s[start++]];
            res = max(end - start + 1, res);
            ++end;
        }

        return res;
    }
};