Longest substring with at most k distinct characters

Hash Table String Sliding Window

49.9% acceptance

Mar 31, 2026

2904

No description available.

Solution

Rust

Time O(n²)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn length_of_longest_substring_k_distinct(s: String, k: i32) -> i32 {
    if k == 0 {
      return 0;
    }
    let k = k as usize;
    let bytes = s.as_bytes();
    let mut count = [0i32; 128];
    let mut distinct = 0usize;
    let mut left = 0usize;
    let mut ans = 0usize;
    for right in 0..bytes.len() {
      let c = bytes[right] as usize;
      if count[c] == 0 {
        distinct += 1;
      }
      count[c] += 1;
      while distinct > k {
        let lc = bytes[left] as usize;
        count[lc] -= 1;
        if count[lc] == 0 {
          distinct -= 1;
        }
        left += 1;
      }
      ans = ans.max(right - left + 1);
    }
    ans as i32
  }
}