3. Longest Substring Without Repeating Characters – Solution

Difficulty: medium
Topics: Hash Table, String, Sliding Window

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.

Solution

It’s easy to come up with a O(n^2) approach. Just check the length of longest substring starting from 0 to end.

O(n) approach needs more thinking:

int lengthOfLongestSubstring(string s) {
        
        map<char, int> charMap;
        int start = -1;
        int maxLen = 0;
        
        for (int i = 0; i < s.size(); i++) {
            if (charMap.count(s[i]) != 0) {
                start = max(start, charMap[s[i]]);
            }
            charMap[s[i]] = i;
            maxLen = max(maxLen, i-start);
        }
        
        return maxLen;
    }

This puts the index of where characters appears in a hashmap. So as we iterate from 0 to end, we can know where that character appeared last time and find the length. Each time we recalculate the max.

Reflection

interesting concept to blackbox:

• whenever finding a maximum value through iteration, let’s use maxval = max(maxval, newval)
• use hashmap to store the value and its frequency, or value and index.
• If the value is a character or linear sequence number, it can be stored in an array as well. But using hashmap can be more efficient space-wise.