3. Longest Substring Without Repeating Characters

1. Description

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

2. Example

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.

Example 4:
Input: s = ""
Output: 0

3. Constraints

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

4. Solutions

Sliding Window

n = str.size()
Time complexity: O(n)
Space complexity: O(1)

class Solution {
public:
    int lengthOfLongestSubstring(const string &str) {
        int max_length = 0;
        map<char, int> letters_count;
        for(int i = 0, j = 0; j < str.size(); ++j) {
            ++letters_count[str[j]];

            while(letters_count[str[j]] > 1) {
                --letters_count[str[i]];
                ++i;
            }

            max_length = max(j - i + 1, max_length);
        }

        return max_length;
    }
};