Cpp, one pass solution(while two points solution is two pass)


  • 0
    I

    use hash to keep the last index of chars.

    And have a sum to keep cur two chars. So it can use sum to get the last index of other char.

    class Solution {
    public:
        int lengthOfLongestSubstringTwoDistinct(string s) {
            int sum = 0;
            int map[256];
            memset(map,-1,sizeof(map));
            int last = -1;
            int ret = 0;
            int cnt = 0;
            for(int i = 0;i < s.length(); i++){
                if(map[s[i]] >= 0){
                    map[s[i]] = i;
                }else if(cnt < 2){
                    map[s[i]] = i;
                    cnt += 1;
                    sum += s[i];
                }else{
                    char otherchar = sum - s[i-1];
                    last = map[otherchar];
                    map[otherchar] = -1;
                    sum = s[i-1]+s[i];
                    map[s[i]] = i;
                }
                if(i - last > ret){ret = i - last;}
            }
            return ret;
        }
    };

Log in to reply
 

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