2287. 重排字符形成目标字符串

🟢   🔖  哈希表 字符串 计数  🔗 力扣 LeetCode

题目

You are given two 0-indexed strings s and target. You can take some letters from s and rearrange them to form new strings.

Return _themaximum number of copies of _target that can be formed by taking letters froms and rearranging them.

Example 1:

Input: s = "ilovecodingonleetcode", target = "code"

Output: 2

Explanation:

For the first copy of "code", take the letters at indices 4, 5, 6, and 7.

For the second copy of "code", take the letters at indices 17, 18, 19, and 20.

The strings that are formed are "ecod" and "code" which can both be rearranged into "code".

We can make at most two copies of "code", so we return 2.

Example 2:

Input: s = "abcba", target = "abc"

Output: 1

Explanation:

We can make one copy of "abc" by taking the letters at indices 0, 1, and 2.

We can make at most one copy of "abc", so we return 1.

Note that while there is an extra 'a' and 'b' at indices 3 and 4, we cannot reuse the letter 'c' at index 2, so we cannot make a second copy of "abc".

Example 3:

Input: s = "abbaccaddaeea", target = "aaaaa"

Output: 1

Explanation:

We can make one copy of "aaaaa" by taking the letters at indices 0, 3, 6, 9, and 12.

We can make at most one copy of "aaaaa", so we return 1.

Constraints:

• 1 <= s.length <= 100
• 1 <= target.length <= 10
• s and target consist of lowercase English letters.

Note: This question is the same as 1189. Maximum Number of Balloons

题目大意

给你两个下标从 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 由小写英文字母组成

注意： 本题与 1189. “气球” 的最大数量 相同。

解题思路

1. 统计频率：

   • targetMap 记录了 target 中每个字母的频率。
   • freq 记录了 s 中每个字母的频率。

2. 最小次数计算：

   • minCount 初始化为 Infinity，需要找到所有字母能够拼接目标单词的最小次数。
   • 对于 targetMap 中的每个字母，检查它在 s 中的出现次数。
   • 如果 s 中没有某个字母，则直接返回 0。
   • 用 Math.floor(freq[char] / count) 计算 s 中该字母能提供的最大次数，并更新 minCount。

3. 返回结果：

   • 最终返回 minCount，即拼凑 target 单词的最大次数。

复杂度分析

• 时间复杂度：O(n + m)，其中 n 是 s 的长度，m 是 target 的长度。
  • 统计频率的时间复杂度为 O(n + m)。
  • 遍历目标字符串 target 计算最小次数，时间复杂度为 O(m)。
  • 总体时间复杂度为 O(n + m)。
• 空间复杂度：O(1)，使用了两个 Map 来记录字母的频率，最多有 26 个字母。

代码

/**
 * @param {string} s
 * @param {string} target
 * @return {number}
 */
var rearrangeCharacters = function (s, target) {
	// 统计 target 中每个字符的频率
	let targetMap = new Map();
	for (let char of target) {
		targetMap.set(char, (targetMap.get(char) || 0) + 1);
	}

	// 统计 s 中每个字符的频率
	let freq = new Map();
	for (let char of s) {
		freq.set(char, (freq.get(char) || 0) + 1);
	}

	// 计算可以拼凑 target 中单词的最大次数
	let minCount = Infinity;
	for (let [char, count] of targetMap.entries()) {
		// 如果 s 中没有 target 中的某个字母，直接返回 0
		if (!freq.has(char)) return 0;
		minCount = Math.min(minCount, Math.floor(freq.get(char) / count));
	}
	return minCount;
};

相关题目

题号	标题	题解	标签	难度	力扣
1160	拼写单词	[✓]	数组 哈希表 字符串 1+	🟢	🀄️ 🔗
1297	子串的最大出现次数		哈希表 字符串 滑动窗口	🟠	🀄️ 🔗