My AC but not efficient solution. Does anyone give me a better idea


  • 0
    Y

    My idea is straightforward.
    like a string: aabbbcd
    when detect the first 'c', my hashmap's size is 2, then I will store the size, and start from the first b rather than the second a(use a variable to store the first b's position).
    This solution might be better than brute force one, but not good enough. And runs too slow: 44ms
    Does someone give me a better idea?
    Here is my code:

    class Solution {
    public:
        int lengthOfLongestSubstringTwoDistinct(string s) {
      		unordered_set<char> str_map;
      		unordered_set<char>::iterator it;
      		int max = 0;
      		int count = 0;
      		int position = 0;
      		for (int i = 0; i < s.length(); ++i) {
      			it = str_map.find(s[i]);
      			if (it != str_map.end()) {
      				/* find it */
      				++count;
      				if (s[i] == s[i-1])
      					;
      				else
      					position = i;
      			}
      			else {
      				/* clear the hashmap */
      				if (str_map.size() == 2) {
      					i = position;
      					str_map.clear();
      					str_map.insert(s[i]);
      					if (count > max)
      						max = count;
      					count = 1;
      				}
      				else {
      					++count;
      					position = i;
      					str_map.insert(s[i]);
      				}
      			}
      		}
      		if (count > max)
      			return count;
    		else
    			return max;      
        }
    };

Log in to reply
 

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