3. Longest Substring Without Repeating Characters

3. Longest Substring Without Repeating Characters (Medium)

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.

Companies:
Amazon, Google, Bloomberg, Facebook, Microsoft, Adobe, Apple, Alibaba, Uber, ByteDance, Cisco, Huawei, Zillow, Yahoo, Grab, eBay, Twitch, Atlassian

Related Topics:
Hash Table, Two Pointers, String, Sliding Window

Similar Questions:

• Longest Substring with At Most Two Distinct Characters (Hard)
• Longest Substring with At Most K Distinct Characters (Hard)
• Subarrays with K Different Integers (Hard)

Solution 1. Hash Map

// OJ: https://leetcode.com/problems/longest-substring-without-repeating-characters/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(C) where C is the range of character set
// Ref: https://discuss.leetcode.com/topic/24739/c-code-in-9-lines
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int ans = 0, start = -1;
        vector<int> m(128, -1);
        for (int i = 0; i < s.size(); ++i) {
            start = max(start, m[s[i]]);
            m[s[i]] = i;
            ans = max(ans, i - start);
        }
        return ans;
    }
};

Solution 2. Sliding Window

Check out "C++ Maximum Sliding Window Cheatsheet Template!".

Shrinkable Sliding Window:

// OJ: https://leetcode.com/problems/longest-substring-without-repeating-characters/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(C)
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int i = 0, j = 0, N = s.size(), cnt[128] = {}, dup = 0, ans = 0;
        while (j < N) {
            dup += ++cnt[s[j++]] == 2;
            while (dup) dup -= --cnt[s[i++]] == 1;
            ans = max(ans, j - i);
        }
        return ans;
    }
};

Non-shrinable Sliding Window:

// OJ: https://leetcode.com/problems/longest-substring-without-repeating-characters/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(C)
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int i = 0, j = 0, N = s.size(), cnt[128] = {}, dup = 0;
        while (j < N) {
            dup += ++cnt[s[j++]] == 2;
            if (dup) dup -= --cnt[s[i++]] == 1;
        }
        return j - i;
    }
};

Discuss

https://leetcode.com/problems/longest-substring-without-repeating-characters/discuss/1499836/C%2B%2B-Sliding-Window-(%2B-Cheat-Sheet)