Longest Substring with At Most K Distinct Characters

Given a string s and an integer k, return the length of the longest substring that contains at most k distinct characters.

If k is 0 or the string is empty, return 0.

Example 1:
Input: s = "eceba", k = 2 → Output: 3
Explanation: The answer is "ece" with 2 distinct characters.

Example 2:
Input: s = "aa", k = 1 → Output: 2
Explanation: The entire string has only one distinct character.

Understanding the Problem

We are given a string s and an integer k. Our goal is to find the length of the longest substring of s that contains at most k distinct characters.

Think of a substring as a piece of the original string that comes in a continuous block. The constraint is that this block can have at most k different letters.

If k is 0 or if the string is empty, it means no characters can be part of the substring — so we return 0 immediately.

We will use the sliding window technique with two pointers (start and end) to maintain a valid window and a hash map to count character frequency.

Step-by-Step Solution with Example

Step 1: Initialize

We start by initializing:

• A map called charFreq to store how many times each character appears in our window.
• start = 0 and end will iterate through the string.
• maxLen = 0 to track the longest valid substring.

Step 2: Traverse the String

We iterate through the string one character at a time using end. At each step:

• Add s[end] to the charFreq map and update its count.
• Check: if the number of distinct keys in charFreq exceeds k, the window is no longer valid.

Step 3: Shrink Window

While the window is invalid (i.e., we have more than k distinct characters), we shrink it from the left:

• Decrease the count of s[start] in the map.
• If the count becomes zero, remove that character from the map.
• Move start forward by one.

Step 4: Update Max Length

At each valid window, calculate the window size (end - start + 1) and update maxLen if it's larger than the previous value.

Step 5: Example Walkthrough

Let's take s = "eceba", k = 2

Window: "e" → {'e':1} → valid → maxLen = 1
Window: "ec" → {'e':1, 'c':1} → valid → maxLen = 2
Window: "ece" → {'e':2, 'c':1} → valid → maxLen = 3
Window: "eceb" → {'e':2, 'c':1, 'b':1} → invalid → shrink
  Shrink to "ceb" → remove 'e' once → {'e':1, 'c':1, 'b':1}
  Shrink to "eb" → remove 'c' completely → {'e':1, 'b':1}
Window now valid again → maxLen remains 3
Continue to next char 'a' → invalid → shrink again...
Final result: 3 (substring "ece")

Edge Cases

• s = "", k = 2 → Output: 0 (empty input)
• s = "a", k = 0 → Output: 0 (k is 0, no characters allowed)
• s = "abc", k = 3 → Output: 3 (all characters fit)
• s = "aaaa", k = 1 → Output: 4 (only one character used)

Final Thoughts

This is a classic sliding window problem where we maintain a valid window using two pointers and a character frequency map. The key is to efficiently expand and contract the window so that it always satisfies the condition of having at most k distinct characters.

With a good understanding of this problem, you'll build intuition for many real-world string-processing tasks and interview questions.

1. Initialize a hash map charFreq to store frequency of characters in the current window.
2. Use two pointers: start for the beginning of the window, and end for the current index while expanding the window.
3. Initialize maxLen = 0 to store the maximum length of a valid substring.
4. Traverse the string with end from 0 to s.length - 1:
5. → Add s[end] to charFreq and increment its count.
6. → While the size of charFreq > k, shrink the window from the left:
7.     • Decrease the frequency of s[start] in charFreq.
8.     • If frequency becomes 0, remove s[start] from charFreq.
9.     • Increment start to shrink the window.
10. → Update maxLen = max(maxLen, end - start + 1).
11. After traversal, return maxLen as the final result.

#include <stdio.h>
#include <string.h>
#include <stdbool.h>

#define MAX_CHAR 256

int longestSubstringKDistinct(const char* s, int k) {
    if (k == 0 || s[0] == '\0') return 0;

    int freq[MAX_CHAR] = {0};
    int distinctCount = 0, maxLen = 0;
    int start = 0, end = 0, len = strlen(s);

    while (end < len) {
        if (freq[(unsigned char)s[end]] == 0) distinctCount++;
        freq[(unsigned char)s[end]]++;

        while (distinctCount > k) {
            freq[(unsigned char)s[start]]--;
            if (freq[(unsigned char)s[start]] == 0) distinctCount--;
            start++;
        }

        int windowLen = end - start + 1;
        if (windowLen > maxLen) maxLen = windowLen;
        end++;
    }
    return maxLen;
}

int main() {
    const char* s1 = "eceba";
    int k1 = 2;
    printf("Longest substring length for '%s' with at most %d distinct chars: %d\n", s1, k1, longestSubstringKDistinct(s1, k1));

    const char* s2 = "aa";
    int k2 = 1;
    printf("Longest substring length for '%s' with at most %d distinct chars: %d\n", s2, k2, longestSubstringKDistinct(s2, k2));

    return 0;
}

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int longestSubstringKDistinct(const string& s, int k) {
    if (k == 0 || s.empty()) return 0;

    unordered_map<char, int> charFreq;
    int start = 0, maxLen = 0;

    for (int end = 0; end < (int)s.size(); ++end) {
        charFreq[s[end]]++;

        while ((int)charFreq.size() > k) {
            charFreq[s[start]]--;
            if (charFreq[s[start]] == 0) charFreq.erase(s[start]);
            start++;
        }

        maxLen = max(maxLen, end - start + 1);
    }
    return maxLen;
}

int main() {
    cout << "Longest substring length for 'eceba' with at most 2 distinct chars: "
         << longestSubstringKDistinct("eceba", 2) << endl;
    cout << "Longest substring length for 'aa' with at most 1 distinct chars: "
         << longestSubstringKDistinct("aa", 1) << endl;
    return 0;
}

def longest_substring_k_distinct(s: str, k: int) -> int:
    if k == 0 or not s:
        return 0

    char_freq = {}
    start = 0
    max_len = 0

    for end in range(len(s)):
        char_freq[s[end]] = char_freq.get(s[end], 0) + 1

        while len(char_freq) > k:
            char_freq[s[start]] -= 1
            if char_freq[s[start]] == 0:
                del char_freq[s[start]]
            start += 1

        max_len = max(max_len, end - start + 1)

    return max_len

# Example usage
print(longest_substring_k_distinct("eceba", 2))  # Output: 3
print(longest_substring_k_distinct("aa", 1))    # Output: 2

import java.util.HashMap;

public class LongestSubstringKDistinct {
    public static int lengthOfLongestSubstringKDistinct(String s, int k) {
        if (k == 0 || s.isEmpty()) return 0;

        HashMap<Character, Integer> charFreq = new HashMap<>();
        int start = 0, maxLen = 0;

        for (int end = 0; end < s.length(); end++) {
            char c = s.charAt(end);
            charFreq.put(c, charFreq.getOrDefault(c, 0) + 1);

            while (charFreq.size() > k) {
                char startChar = s.charAt(start);
                charFreq.put(startChar, charFreq.get(startChar) - 1);
                if (charFreq.get(startChar) == 0) {
                    charFreq.remove(startChar);
                }
                start++;
            }

            maxLen = Math.max(maxLen, end - start + 1);
        }
        return maxLen;
    }

    public static void main(String[] args) {
        System.out.println(lengthOfLongestSubstringKDistinct("eceba", 2)); // 3
        System.out.println(lengthOfLongestSubstringKDistinct("aa", 1));   // 2
    }
}

function longestSubstringKDistinct(s, k) {
  if (k === 0 || s.length === 0) return 0;

  const charFreq = new Map();
  let start = 0, maxLen = 0;

  for (let end = 0; end < s.length; end++) {
    const endChar = s[end];
    charFreq.set(endChar, (charFreq.get(endChar) || 0) + 1);

    while (charFreq.size > k) {
      const startChar = s[start];
      charFreq.set(startChar, charFreq.get(startChar) - 1);
      if (charFreq.get(startChar) === 0) {
        charFreq.delete(startChar);
      }
      start++;
    }

    maxLen = Math.max(maxLen, end - start + 1);
  }

  return maxLen;
}

// Example usage:
console.log(longestSubstringKDistinct("eceba", 2)); // 3
console.log(longestSubstringKDistinct("aa", 1));   // 2

package main

import "fmt"

func longestSubstringKDistinct(s string, k int) int {
    if k == 0 || len(s) == 0 {
        return 0
    }

    freq := make(map[rune]int)
    start, maxLen := 0, 0

    for end, ch := range s {
        freq[ch]++

        for len(freq) > k {
            startChar := rune(s[start])
            freq[startChar]--
            if freq[startChar] == 0 {
                delete(freq, startChar)
            }
            start++
        }

        windowLen := end - start + 1
        if windowLen > maxLen {
            maxLen = windowLen
        }
    }

    return maxLen
}

func main() {
    fmt.Println(longestSubstringKDistinct("eceba", 2)) // 3
    fmt.Println(longestSubstringKDistinct("aa", 1))   // 2
}

use std::collections::HashMap;

fn longest_substring_k_distinct(s: &str, k: usize) -> usize {
    if k == 0 || s.is_empty() {
        return 0;
    }

    let mut freq: HashMap<char, usize> = HashMap::new();
    let mut start = 0;
    let mut max_len = 0;

    let chars: Vec<char> = s.chars().collect();

    for end in 0..chars.len() {
        *freq.entry(chars[end]).or_insert(0) += 1;

        while freq.len() > k {
            let start_char = chars[start];
            if let Some(count) = freq.get_mut(&start_char) {
                *count -= 1;
                if *count == 0 {
                    freq.remove(&start_char);
                }
            }
            start += 1;
        }

        max_len = max_len.max(end - start + 1);
    }

    max_len
}

fn main() {
    println!("{}", longest_substring_k_distinct("eceba", 2)); // 3
    println!("{}", longest_substring_k_distinct("aa", 1));   // 2
}

fun longestSubstringKDistinct(s: String, k: Int): Int {
    if (k == 0 || s.isEmpty()) return 0

    val charFreq = mutableMapOf<Char, Int>()
    var start = 0
    var maxLen = 0

    for (end in s.indices) {
        val endChar = s[end]
        charFreq[endChar] = charFreq.getOrDefault(endChar, 0) + 1

        while (charFreq.size > k) {
            val startChar = s[start]
            charFreq[startChar] = charFreq[startChar]!! - 1
            if (charFreq[startChar] == 0) {
                charFreq.remove(startChar)
            }
            start++
        }

        maxLen = maxOf(maxLen, end - start + 1)
    }

    return maxLen
}

fun main() {
    println(longestSubstringKDistinct("eceba", 2)) // 3
    println(longestSubstringKDistinct("aa", 1))   // 2
}

func longestSubstringKDistinct(_ s: String, _ k: Int) -> Int {
    if k == 0 || s.isEmpty { return 0 }

    var charFreq = [Character: Int]()
    var start = s.startIndex
    var maxLen = 0

    for end in s.indices {
        let endChar = s[end]
        charFreq[endChar, default: 0] += 1

        while charFreq.count > k {
            let startChar = s[start]
            charFreq[startChar]! -= 1
            if charFreq[startChar] == 0 {
                charFreq.removeValue(forKey: startChar)
            }
            start = s.index(after: start)
        }

        let windowLen = s.distance(from: start, to: end) + 1
        maxLen = max(maxLen, windowLen)
    }

    return maxLen
}

print(longestSubstringKDistinct("eceba", 2)) // 3
print(longestSubstringKDistinct("aa", 1))   // 2

function longestSubstringKDistinct(s: string, k: number): number {
  if (k === 0 || s.length === 0) return 0;

  const charFreq: Record<string, number> = {};
  let start = 0;
  let maxLen = 0;

  for (let end = 0; end < s.length; end++) {
    const endChar = s[end];
    charFreq[endChar] = (charFreq[endChar] || 0) + 1;

    while (Object.keys(charFreq).length > k) {
      const startChar = s[start];
      charFreq[startChar]--;
      if (charFreq[startChar] === 0) {
        delete charFreq[startChar];
      }
      start++;
    }

    maxLen = Math.max(maxLen, end - start + 1);
  }

  return maxLen;
}

// Example usage
console.log(longestSubstringKDistinct("eceba", 2)); // 3
console.log(longestSubstringKDistinct("aa", 1));   // 2;

Time complexity

Space complexity

O(k)

The hash map stores at most k characters and their frequencies at any point, so space usage grows with k.