Welcome to Subscribe On Youtube

3662. Filter Characters by Frequency 🔒

Description

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

Solutions

Solution 1: Counting

First, we iterate through the string $s$ and count the frequency of each character, storing the results in a hash table or array $\textit{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.

  • class Solution {
    public String filterCharacters(String s, int k) {
        int[] cnt = new int[26];
        for (char c : s.toCharArray()) {
            ++cnt[c - 'a'];
        }
        StringBuilder ans = new StringBuilder();
        for (char c : s.toCharArray()) {
            if (cnt[c - 'a'] < k) {
                ans.append(c);
            }
        }
        return ans.toString();
    }
}


  • class Solution {
public:
    string filterCharacters(string s, int k) {
        int cnt[26]{};
        for (char c : s) {
            ++cnt[c - 'a'];
        }
        string ans;
        for (char c : s) {
            if (cnt[c - 'a'] < k) {
                ans.push_back(c);
            }
        }
        return ans;
    }
};


  • class Solution:
    def filterCharacters(self, s: str, k: int) -> str:
        cnt = Counter(s)
        ans = []
        for c in s:
            if cnt[c] < k:
                ans.append(c)
        return "".join(ans)


  • func filterCharacters(s string, k int) string {
	cnt := [26]int{}
	for _, c := range s {
		cnt[c-'a']++
	}
	ans := []rune{}
	for _, c := range s {
		if cnt[c-'a'] < k {
			ans = append(ans, c)
		}
	}
	return string(ans)
}


  • function filterCharacters(s: string, k: number): string {
    const cnt: Record<string, number> = {};
    for (const c of s) {
        cnt[c] = (cnt[c] || 0) + 1;
    }
    const ans: string[] = [];
    for (const c of s) {
        if (cnt[c] < k) {
            ans.push(c);
        }
    }
    return ans.join('');
}

All Problems

All Solutions