3. Longest Substring Without Repeating Characters (Medium)

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

Examples:

Given"abcabcbb", the answer is"abc", which the length is 3.

Given"bbbbb", the answer is"b", with the length of 1.

Given"pwwkew", 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 1: Sliding Window

The above solution requires at most 2n steps. In fact, it could be optimized to require only n steps. Instead of using a set to tell if a character exists or not, we could define a mapping of the characters to its index. Then we can skip the characters immediately when we found a repeated character.

The reason is that if $$s[j]$$ have a duplicate in the range $$[i,j)$$ with index $$j'$$, we don't need to increase $$i$$ little by little. We can skip all the elements in the range $$[i,j']$$ and let $$i$$ to be $$j' + 1$$ directly.

Complexity Analysis

• Time complexity : $$O(n)$$. Index $$j$$ will iteraten $$n$$ times.

• Space complexity (HashMap) : $$O(min(m,n)$$. Same as the previous approach.

• Space complexity (Table): $$O(m)$$. $$m$$ is the size of the charset.

int lengthOfLongestSubstring(string s) {
    vector<int> m(128, -1); // idx
    int start = -1, res = 0;
    for (int i = 0; i < s.size(); ++i) {
        start = max(start, m[s[i]]);
        res = max(res, i-start);
        m[s[i]] = i;
    }
    return res;
}

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int i = 0, res = 0;
        vector<int> v(128, 0);
        for (int j = 0; j < s.size(); ++j) {
            i = max(i, v[s[j]]); // new start position
            res = max(res, j-i+1);
            v[s[j]] = j+1;
        }
        return res;
    }
};

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int res = 0, cnt = 0, start = 0;
        vector<int> v(128,-1);
        for (int i = 0; i < s.size(); ++i) {
            if (v[s[i]] != -1 && start <= v[s[i]]) {
                start = v[s[i]]+1;
                v[s[i]] = i;
            } else {
                v[s[i]] = i;
                res = max(res, i-start+1);
            }
        }
        return res;
    }
};

Solution 2: Hash Table, Two Pointers 19ms

using substring problem template

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        vector<int> map(128,0);
        int left = 0, right = 0, maxlen = 0, count = 0;
        while (right < s.size()) {
            if (map[s[right++]]++ > 0) ++count; //invalid
            while (count > 0) { 
                if (map[s[left++]]-- > 1) --count;
            }
            // valid
            maxlen = max(maxlen, right-left);
        }
        return maxlen;
    }
};