Problem

Find the longest substring in a given string that doesn’t contain any repeating characters, and return the length of this substring.

Approach

It’s easy to come up with an algorithm with O(n^2) time complexity. Iterate through each character, and for each character as a starting point, determine the length of the longest substring without repeating characters. Then output the maximum length among all substrings.

Runtime: 600ms, beats 0% of submissions

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int ret = 0;
        for(int i=0; i<s.size(); i++){
            unordered_set<char> buff;
            for(int j=i; j<s.size(); j++){
                if(buff.count(s[j]) == 0) buff.insert(s[j]);
                else break;
            }
            if(buff.size() > ret) ret = buff.size();
        }
        return ret;
    }
};

Improvement

As we can see, the algorithm above is quite inefficient and is one of the slowest algorithms in the world. When searching for substrings, we need to set a starting point. This starting point is the position where, up to the current iteration, we have the longest substring without repeating characters. By subtracting this position from the current iteration position, we can get the length of the longest substring.

Runtime: 15ms, beats 96% of submissions

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        vector<int> lastPos(260, -1);
        int length = s.size();
        int ret = 0;
        int start = 0;
        for(int i=0; i<length; i++)
        {
            char c = s[i];
            if(lastPos[c]+1 > start) start = lastPos[c] + 1;
            if(i-start+1 > ret) ret = i-start+1;
            lastPos[c] = i;
        }
        
        return ret;
    }
};