Filter characters by frequency

Hash Table String Counting

86.8% acceptance

Mar 31, 2026

You are given a string s consisting of lowercase English letters and an integer k. Your task is to construct a new string that contains only those characters from s which appear fewer than k times in the entire string. The order of characters in the new string must be the same as their order in s. Return the resulting string. If no characters qualify, return an empty string. Note: Every occurrence of a character that occurs fewer than k times is kept.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn filter_characters(s: String, k: i32) -> String {
    let mut freq = [0i32; 26];
    for b in s.bytes() {
      freq[(b - b'a') as usize] += 1;
    }
    s.chars()
      .filter(|&c| freq[(c as u8 - b'a') as usize] < k)
      .collect()
  }
}