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.
Example 1:
Input: s = "aadbbcccca", k = 3
Output: "dbb"
Explanation:
Character frequencies in s:
'a' appears 3 times'd' appears 1 time'b' appears 2 times'c' appears 4 timesOnly 'd' and 'b' appear fewer than 3 times. Preserving their order, the result is "dbb".
Example 2:
Input: s = "xyz", k = 2
Output: "xyz"
Explanation:
All characters ('x', 'y', 'z') appear exactly once, which is fewer than 2. Thus the whole string is returned.
Constraints:
1 <= s.length <= 100s consists of lowercase English letters.1 <= k <= s.lengthProblem Overview: You are given a string and need to filter characters based on how often they appear. The task is to count character frequencies and keep only those that satisfy the required frequency condition, producing a filtered result string.
Approach 1: Recounting for Each Character (Brute Force) (Time: O(n^2), Space: O(1))
A straightforward approach checks the frequency of each character by scanning the entire string every time you encounter it. For each position i, iterate through the string again and count how many times s[i] appears. Based on that count, decide whether to keep or discard the character. This method avoids extra memory but repeatedly scans the same data, leading to quadratic time complexity. It works for very small strings but becomes inefficient quickly.
Approach 2: Hash Map Frequency Counting (Time: O(n), Space: O(k))
The efficient solution uses a frequency table implemented with a hash table. First iterate through the string and count occurrences of each character using a map like freq[c]++. Then perform a second pass through the string and append characters whose frequency meets the required condition. Each lookup in the map is constant time, so the entire algorithm runs in linear time. This technique is the standard pattern for string problems that involve counting or filtering characters.
This approach works because counting once avoids repeated scans. The map stores at most k unique characters (often limited to 26 for lowercase letters), keeping memory usage small. Many interview problems rely on the same pattern: build a frequency map, then process the string using those counts. The technique falls under the broader category of counting problems.
Recommended for interviews: Interviewers expect the hash map counting solution. Showing the brute force approach demonstrates baseline reasoning, but the optimal solution proves you understand how to trade a small amount of memory for a linear-time algorithm.
First, we iterate through the string s and count the frequency of each character, storing the results in a hash table or array cnt.
Then, we iterate through the string s again, adding characters whose frequency is less than k to the result string. Finally, we return the result string.
The time complexity is O(n), where n is the length of the string s. The space complexity is O(|\Sigma|), where \Sigma is the size of the character set.
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recount Frequency for Each Character (Brute Force) | O(n^2) | O(1) | Small inputs or when avoiding extra memory is required |
| Hash Map Frequency Counting | O(n) | O(k) | General case; best performance for large strings |
Practice Filter Characters by Frequency with our built-in code editor and test cases.
Practice on FleetCode