Description

tags: Linked list, Math

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.

Solution

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int l = 0, maxLen = 0;
        map<char, vector<int>> dict;

        for (int r=0; r<s.size(); r++) {
            if (dict.find(s[r]) != dict.end()) {
                l = max(l, dict[s[r]].back() + 1);
            }
            dict[s[r]].push_back(r);
            maxLen = max(maxLen, r - l + 1);
        }
        return maxLen;
    }
};

Analysis

Time:
Space: