Skip to main content
Talentd

Filter Characters by Frequency - Solution & Explanation

EasyPremiumFree on FleetCodeHash TableStringCounting6 min readAsked at: Opentext
Practice this problem

Problem Statement

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 times

Only '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 <= 100
  • s consists of lowercase English letters.
  • 1 <= k <= s.length

Approach Overview

Problem 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.

Solution

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen 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 CountingO(n)O(k)General case; best performance for large strings

Frequently Asked Questions

Is Filter Characters by Frequency easy or hard?
Filter Characters by Frequency is typically classified as an Easy problem. The core idea is straightforward: count character frequencies and filter the string based on those counts. The challenge mainly involves recognizing the hash map counting pattern.
Filter Characters by Frequency Python/Java solution
Both Python and Java implementations use the same strategy: build a frequency map (Python dictionary or Java HashMap) and then iterate through the string to build the filtered result. The algorithm runs in O(n) time and works similarly in C++, Go, and TypeScript.
How to solve Filter Characters by Frequency in O(n)?
Use a hash map to count occurrences of each character while scanning the string once. After building the frequency table, iterate through the string again and append characters whose counts meet the required threshold. Hash lookups are constant time, so the overall complexity remains linear.
What is the best approach for Filter Characters by Frequency?
The hash map frequency counting approach is the most efficient. First count how many times each character appears, then iterate through the string and keep characters that satisfy the frequency condition. This runs in O(n) time with O(k) space, where k is the number of distinct characters.
Is Filter Characters by Frequency asked at Google/Amazon/Meta?
Frequency-counting string problems are common in interviews at companies like Google, Amazon, and Meta. While the exact problem may vary, the underlying pattern of counting characters with a hash map and filtering based on frequency appears frequently in coding interviews.
What data structure is used in Filter Characters by Frequency?
The primary data structure is a hash table (or dictionary) that maps each character to its frequency. This allows constant-time updates and lookups while counting characters and deciding whether to include them in the result.
What is the time complexity of Filter Characters by Frequency?
The optimal solution runs in O(n) time because the string is scanned twice: once to build the frequency map and once to construct the filtered result. Space complexity is O(k), where k represents the number of unique characters stored in the hash map.

Ready to solve this problem?

Practice Filter Characters by Frequency with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Longest Substring Without Repeating Characters