Longest substring with at least k repeating characters

Hash Table String Divide and Conquer Sliding Window

46.1% acceptance

Jan 12, 2026

6700

568

Given a string s and an integer k, return the length of the longest substring of s such that the frequency of each character in this substring is greater than or equal to k. if no such substring exists, return 0.

Solution

Rust

Time O(2^n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn longest_substring(s: String, k: i32) -> i32 {
    if s.len() < k as usize {
      return 0;
    }
    
    let mut counts = [0; 26];
    for b in s.bytes() {
      counts[(b - b'a') as usize] += 1;
    }
    
    for (i, b) in s.bytes().enumerate() {
      if counts[(b - b'a') as usize] < k {
        let left = Self::longest_substring(s[..i].to_string(), k);
        let right = Self::longest_substring(s[i + 1..].to_string(), k);
        return left.max(right);
      }
    }
    
    s.len() as i32
  }
}