Shortest Solution, Easy to understand


  • 1
    class Solution {
    public:
        int lengthOfLongestSubstring(string s) {
            if(s.size() <=1) return s.size();
            vector<int> lastPos(256,0); //store the last position of each charater as it scans the string.
            int max = 1; int lastMax = 1; lastPos[s[0]] = 1;
            //scan the string one by one.
            for(int i = 1; i < s.size(); i++){
                lastMax = min(lastMax+1,i+1-lastPos[s[i]]);
                lastPos[s[i]] = i+1;
                if(lastMax > max) max = lastMax;
            }
            return max;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.