重排字符形成目标字符串

标签: 哈希表 字符串 计数

难度: Easy

给你两个下标从 0 开始的字符串 s 和 target 。你可以从 s 取出一些字符并将其重排，得到若干新的字符串。

从 s 中取出字符并重新排列，返回可以形成 target 的 最大 副本数。

示例 1：

输入：s = "ilovecodingonleetcode", target = "code"
输出：2
解释：
对于 "code" 的第 1 个副本，选取下标为 4 、5 、6 和 7 的字符。
对于 "code" 的第 2 个副本，选取下标为 17 、18 、19 和 20 的字符。
形成的字符串分别是 "ecod" 和 "code" ，都可以重排为 "code" 。
可以形成最多 2 个 "code" 的副本，所以返回 2 。

示例 2：

输入：s = "abcba", target = "abc"
输出：1
解释：
选取下标为 0 、1 和 2 的字符，可以形成 "abc" 的 1 个副本。 
可以形成最多 1 个 "abc" 的副本，所以返回 1 。
注意，尽管下标 3 和 4 分别有额外的 'a' 和 'b' ，但不能重用下标 2 处的 'c' ，所以无法形成 "abc" 的第 2 个副本。

示例 3：

输入：s = "abbaccaddaeea", target = "aaaaa"
输出：1
解释：
选取下标为 0 、3 、6 、9 和 12 的字符，可以形成 "aaaaa" 的 1 个副本。
可以形成最多 1 个 "aaaaa" 的副本，所以返回 1 。

提示：

  • 1 <= s.length <= 100
  • 1 <= target.length <= 10
  • s 和 target 由小写英文字母组成

Submission

运行时间: 27 ms

内存: 16.0 MB

class Solution:
    def rearrangeCharacters(self, s: str, target: str) -> int:
        mp = {}
        for i in s:
            mp[i] = mp.get(i, 0) + 1
        mp_t = {}
        for i in target:
            mp_t[i] = mp_t.get(i, 0) + 1
        res = len(s)
        for key in mp_t:
            res = min(res, mp.get(key, 0) // mp_t[key])
        return res

Explain

这个题解的思路是使用哈希表来统计字符串 s 和 target 中每个字符出现的次数。首先，遍历字符串 s，用一个哈希表 mp 来记录每个字符的出现次数。然后，遍历字符串 target，用另一个哈希表 mp_t 来记录 target 中每个字符的出现次数。接着，对于 target 中的每一个字符，计算 s 中对应字符的数量除以 target 中该字符的数量，这个商表示 s 中这个字符能为构成 target 提供的最大副本数。最后，取这些商的最小值，即为答案。这样可以确保 target 的每个字符都有足够的数量来重复构成 target 指定的次数。

时间复杂度: O(n + m)

空间复杂度: O(1)

class Solution:
    def rearrangeCharacters(self, s: str, target: str) -> int:
        mp = {}
        for i in s:
            mp[i] = mp.get(i, 0) + 1  # 统计 s 中每个字符的出现次数
        mp_t = {}
        for i in target:
            mp_t[i] = mp_t.get(i, 0) + 1  # 统计 target 中每个字符的出现次数
        res = len(s)
        for key in mp_t:
            res = min(res, mp.get(key, 0) // mp_t[key])  # 找出可以构成最多 target 副本的数量
        return res

Explore

在题解中，如果target中的字符在s中不存在，我们通过使用`mp.get(key, 0)`来处理。这里`get`方法的第二个参数0意味着，如果s中没有target中的某个字符，我们将其出现次数视为0。这样，计算`mp.get(key, 0) // mp_t[key]`时，如果s中缺少target中的某个字符，则结果为0，表示不能构成任何一个完整的target副本。

整数除法在这种情况下是准确的，因为我们计算的是能够完全由s中的字符构成target的最大副本数。整数除法`//`确保了我们得到的是一个完整的副本数，没有小数部分。这意味着，即使有更多的字符可能部分地对第N+1个target副本有所贡献，我们只计算完整能够构成的副本数。因此，使用整数除法并不会带来四舍五入的问题，而是确保计算结果的整体性和准确性。

当前的解决方案同样适用于包含其他字符或大小写混合的情况。Python中的字典（哈希表）可以处理任意类型的可哈希键，包括不同的字符和大小写。因此，无论s或target中的字符是什么类型，只要它们能够被统一地识别和比较，当前的算法逻辑就能正确地工作。只需确保在比较和存储这些字符时考虑到它们的实际差异（如大小写敏感性）。

如果target为空字符串，逻辑上我们可以认为s中可以构成无限多个空字符串。在编程实现中，通常会特别处理这种边界情况，返回一个表示无限或者特定大值。在许多实际情况下，可以返回一个大整数或特殊值如`float('inf')`表示无限。然而，具体返回什么值可能取决于问题的具体要求和定义。在没有明确指示的情况下，返回一个大数或者特定的最大值通常是合理的处理方式。