Longest Substring with At Most K Distinct Characters

LeetCode Link

Problem Description

Visit LeetCode for the full problem description.

---

Solutions

Solution 1: C# (Best: 88 ms)

Metric	Value
Runtime	88 ms
Memory	20.9 MB
Date	2019-03-14

Solution

public class Solution {
    public int LengthOfLongestSubstringKDistinct(string s, int k) {
        int n = (s ?? string.Empty).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 > k)
        {
            char temp = s[i];
            wc[temp]--;
            if (wc[temp] == 0) counter--;
            i++;
        }

        len = Math.Max(len, j - i);

    }
    return len;
    }
}

📜 1 more C# submission(s)

Submission (2022-02-08) — 119 ms, 36.4 MB

public class Solution {
    public int LengthOfLongestSubstringKDistinct(string s, int k) {
        Dictionary<char, int> d = new Dictionary<char, int>();
    int result = 0;
    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;
    }
}

---

Complexity Analysis

Approach	Time	Space
Solution	To be analyzed	To be analyzed