3. Longest Substring Without Repeating Characters

• Difficulty: Medium

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

• Similar Questions:

  • Longest Substring with At Most Two Distinct Characters

  • Longest Substring with At Most K Distinct Characters

  • Subarrays with K Different Integers

Problem:

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

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

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

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.

Solutions:

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int charPos[256] {0}; // initialization only for 0, not for other values
        for (int i = 0; i < 256; ++i) charPos[i] = -1;
        int ret = 0;
        int left = 0;
        for (int i = 0; i < s.length(); ++i) {
            char c = s[i];
            if (charPos[c] == -1 || charPos[c] < left) {
                charPos[c] = i;
                ret = max(ret, i - left + 1);
            } else {
                left = max(charPos[c] + 1, left); // first to update left;
                charPos[c] = i;
            }
        }

        return ret;
    }
};