395. Longest Substring with At Least K Repeating Characters

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.

 

Example 1:

Input: s = "aaabb", k = 3
Output: 3
Explanation: The longest substring is "aaa", as 'a' is repeated 3 times.

Example 2:

Input: s = "ababbc", k = 2
Output: 5
Explanation: The longest substring is "ababb", as 'a' is repeated 2 times and 'b' is repeated 3 times.

 

Constraints:

  • 1 <= s.length <= 104
  • s consists of only lowercase English letters.
  • 1 <= k <= 105

Rust Solution

struct Solution;
use std::collections::HashMap;

impl Solution {
    fn longest_substring(s: String, k: i32) -> i32 {
        let mut hm: HashMap<char, usize> = HashMap::new();
        for c in s.chars() {
            *hm.entry(c).or_default() += 1;
        }
        for (c, v) in hm {
            if v < k as usize {
                return s
                    .split_terminator(c)
                    .map(|s| Self::longest_substring(s.to_string(), k))
                    .max()
                    .unwrap();
            }
        }
        s.len() as i32
    }
}

#[test]
fn test() {
    let s = "aaabb".to_string();
    let k = 3;
    let res = 3;
    assert_eq!(Solution::longest_substring(s, k), res);
    let s = "ababbc".to_string();
    let k = 2;
    let res = 5;
    assert_eq!(Solution::longest_substring(s, k), res);
    let s = "ababbc".to_string();
    let k = 3;
    let res = 0;
    assert_eq!(Solution::longest_substring(s, k), res);
}

Having problems with this solution? Click here to submit an issue on github.