3 - Longest Substring Without Repeating Characters

#medium

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

Example 1:
Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Example 2:
Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 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.

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        // 滑動窗口經典題
        int result = 0;
        int left = 0;
        unordered_map<char,int> mp;
        for ( int i = 0; i < s.size(); i++ ) {
            if ( mp.find( s[i] ) != mp.end() ) {
                // mp[s[i]]之前出現過的有沒有出現在滑動窗口裡面
                // 有出現在當前滑動窗口裡 => 代表比left還大
                // 沒出現在當前滑動窗口裡 => left不更新
                left = max( left, mp[s[i]] + 1 ); 
            }

            result = max( result, i - left + 1 );
            mp[s[i]] = i; // 更新該字的index
        }

        return result;
    }
};