Longest Substring with At Most Two Distinct Characters

LeetCode Link

Problem Description

Visit LeetCode for the full problem description.

---

Solutions

Solution 1: C# (Best: 80 ms)

Metric	Value
Runtime	80 ms
Memory	20 MB
Date	2019-03-14

Solution

public class Solution {
    public int LengthOfLongestSubstringTwoDistinct(string s) {
        int n = (s ?? string.Empty).Length;
    if (n <= 2) return s.Length;
    Dictionary<char, int> wc = new Dictionary<char, int>();
    int counter = 0;
    int len = 0;
    int i = 0, j = 0;
    
    while (j < s.Length)
    {
        char c = s[j];
        if (wc.ContainsKey(c))
        {
            wc[c]++;
        }
        else
        {
            wc[c] = 1;          
        }
        if(wc[c]==1) counter++;
        j++;
        while (counter > 2)
        {
            char temp = s[i];
            wc[temp]--;
            if (wc[temp] == 0) counter--;
            i++;
        }
        len = Math.Max(len, j-i);
    
    }
    return len;
    }
}

📜 2 more C# submission(s)

Submission (2022-02-08) — 103 ms, 39.1 MB

public class Solution {
    public int LengthOfLongestSubstringTwoDistinct(string s) {
        Dictionary<char, int> d = new Dictionary<char, int>();
    int result = 0, k=2;
    int i = 0;
    for (int j = 0; j < s.Length; j++)
    {
        if (d.ContainsKey(s[j]))
        {           
            d[s[j]]++;
        }
        else
        {
            d.Add(s[j], 1);
        }
        if(d[s[j]] == 1) k--;

        while (k < 0)
        {
            d[s[i]]--;
            if (d[s[i]] == 0) k++;
            i++;
        }
        result = Math.Max(j - i + 1, result);
    }
    return result;
    }
}

Submission (2022-02-08) — 161 ms, 39.2 MB

public class Solution {
    public int LengthOfLongestSubstringTwoDistinct(string s) {
        Dictionary<char, int> d = new Dictionary<char, int>();
    int result = 0, k=2;
    int i = 0;
    for (int j = 0; j < s.Length; j++)
    {
        if (d.ContainsKey(s[j]))
        {
            if (d[s[j]] == 0) k--;
            d[s[j]]++;
        }
        else
        {
            k--;
            d.Add(s[j], 1);
        }

        while (k < 0)
        {
            d[s[i]]--;
            if (d[s[i]] == 0) k++;
            i++;
        }
        result = Math.Max(j - i + 1, result);
    }
    return result;
    }
}

---

Complexity Analysis

Approach	Time	Space
Solution	To be analyzed	To be analyzed