C# - 2 pointer solution - no hash - beats 100%


  • 0

    Two pointer solution avoids all the hashing and will run quicker. The idea is to track the most recent position of the 2 characters. If you see a 3rd character you will want to drop off the older of the 2. And to calculate your new window size you have a right edge of the current position and a left edge of the value for the character that is dropping off.

        public int LengthOfLongestSubstringTwoDistinct(string s) 
        {
            int left1 = -1;
            int left2 = -1;
            int len = 0;
            int max = 0;
            for (int i = 0; i < s.Length; i++)
            {
                if (left1 == -1 || s[i] == s[left1]) 
                {
                    left1 = i;
                    len++;
                    max = Math.Max(max, len);
                }
                else if (left2 == -1 || s[i] == s[left2]) 
                {
                    left2 = i;
                    len++;
                    max = Math.Max(max, len);
                }
                else
                {
                    if (left1 < left2) { len = i - left1; left1 = i; }
                    else { len = i - left2; left2 = i; }
                }
            }
            return max;
        }
    

Log in to reply
 

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