Elegent and probably shortest solution. With comments


  • 0
    M
    class Solution {
    public:
        int lengthOfLongestSubstring(string s) {
            // set last_osition of all characters to -1. 
            // Just imagine we have all of them at -1 position.
            for(auto &x:last_position){
                x = -1;
            }
            int final_length = 0;
            int starter = -1; // record the last character that has a duplicate later
            for(int i = 0; i < s.size(); ++i){
                // update if necessary
                starter = max(last_position[(unsigned) s[i]], starter);
                last_position[(unsigned) s[i]] = i;
                //  again update if necessary
                final_length = max(final_length, i - starter);
            }
            return final_length;
        }
        int last_position[256];
    };
    

Log in to reply
 

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