Simple C# Solution O(n)


  • 0
    F

    Let us assume that we maintain a map of characters to positions and never let this map grow more than 2 entries long. We maintain a mapping of a character to the position in the string where we last encountered this character in the map (we will see why this is useful later).

    Assuming we maintain such a map, then one simple way to solve this problem is to focus on the point where a sub string, just grows to more than 2 (i.e. 3) distinct characters. Looking at the array index (say k) where this happens and an array index just prior (k - 1) we are guaranteed that at least these two form a sub string with exactly 2 distinct characters. The characters s[k - 1], s[k] represent the two distinct characters of the next sub string we have to examine (here s is the input string).

    However k - 1 may not be the first occurrence of the character at s[k - 1]. In particular we are interested in contiguous occurrences of s[k - 1] that immediately precede k - 1. By definition of the map we are maintaining, the first such contiguous occurrence of s[k - 1] is bound to be 1 after the position that the previous counterpart of s[k -1] was seen at.

    The code below implements this idea.

       public class Solution {
    public int LengthOfLongestSubstringTwoDistinct(string s) {
        if (s.Length < 2) return s.Length;
        var map = new Dictionary<char, int>();
        int start = 0;
        int end = 0;
        int maxLen = 1;
        map[s[0]] = 0;
        
        for (int i = 1; i < s.Length; i++)
        {
            end = i;
            if (!map.ContainsKey(s[i]) && (map.Count == 2))
            {
                var lastKey = s[i - 1];
                var keyToRem = map.Keys.Where ((p)=> p != lastKey).First();
                start = map[keyToRem] + 1;
                map.Remove (keyToRem);
            }
            
            maxLen = Math.Max (maxLen, end - start + 1); 
            map[s[i]] = i;
        }
        return maxLen;
    }
        
    }

Log in to reply
 

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