跳转至

3662. 按频率筛选字符 🔒

题目描述

给定一个包含小写英文字母的字符串 s 和一个整数 k。

你的任务是构造一个新的字符串，其中只包含在整个字符串 s 中出现次数 少于 k 次的字符。新字符串中字符的顺序必须与 s 中的 顺序相同。

返回结果字符串。如果没有字符满足，返回一个空字符串。

注意：出现次数少于 k 次的字符的每次出现都被保留。

 

示例 1：

输入：s = "aadbbcccca", k = 3

输出："dbb"

解释：

s 中字符出现的频率：

  • 'a' 出现 3 次
  • 'd' 出现 1 次
  • 'b' 出现 2 次
  • 'c' 出现 4 次

只有 'd' 和 'b' 出现少于 3 次。保持它们的顺序，结果是 "dbb"。

示例 2：

输入：s = "xyz", k = 2

输出："xyz"

解释：

所有字符（'x'，'y'，'z'）只出现一次，比 2 少。因此返回整个字符串。

 

提示：

  • 1 <= s.length <= 100
  • s 只包含小写英文字母。
  • 1 <= k <= s.length

解法

方法一：计数

我们先遍历字符串 \(s\)，统计每个字符出现的频率，记录在哈希表或数组 \(\textit{cnt}\) 中。

然后再遍历字符串 \(s\)，将出现次数少于 \(k\) 的字符添加到结果字符串中，最后返回结果字符串。

时间复杂度 \(O(n)\)，其中 \(n\) 是字符串 \(s\) 的长度。空间复杂度 \(O(|\Sigma|)\)，其中 \(\Sigma\) 是字符集大小。

1
2
3
4
5
6
7
8
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)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
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();
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
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)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
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('');
}

评论