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.

Description Hints 1 Solution

3662. Filter Characters by Frequency

Easy86.2% acceptance1 companyPremium elsewhere, free here

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

Asked at 1 company

Opentext

Topics

Hints open one at a time

Hint 1

Count the frequency of each character using a 26-entry array or a frequency map, then iterate through the string and append each character whose frequency is less than k to the result.

Still stuck?Read the written solution.

Open solution

LanguageLoading editor…

1class Solution:
  def solve(self):
      pass


Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

"aadbbcccca"
3

Input

"xyz"
2

Your code is saved on this device.Solution