What is the easiest way to solve Rearrange Characters to Make Target String?

Use hash tables to count letters in s and target, then divide available counts by required counts to find the maximum copies.

Can letters in s be reused across multiple copies of target?

No, each letter from s can only be used once per copy of target, which is why we take the minimum across character ratios.

How does this problem relate to Hash Table plus String pattern?

The solution relies on counting character frequencies in both strings efficiently using hash tables and simple arithmetic to compute maximum copies.

What if target contains letters not present in s?

If any letter in target is missing from s, the maximum number of copies is zero.

What is the time complexity for this approach?

It is O(n + m), where n is the length of s and m is the length of target, because each string is scanned once for counting.

#2287

Easy

auto_awesome哈希·表·结合·string

LeetCode 题解工作台

重排字符形成目标字符串

给你两个下标从 0 开始的字符串 s 和 target 。你可以从 s 取出一些字符并将其重排，得到若干新的字符串。从 s 中取出字符并重新排列，返回可以形成 target 的最大副本数。示例 1：输入： s = "ilovecodingonleetcode", target = "cod…

哈希表字符串计数

题目描述

给你两个下标从 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. “气球” 的最大数量相同。

lightbulb

解题思路

方法一：计数

我们统计字符串 $\textit{s}$ 和 $\textit{target}$ 中每个字符出现的次数，记为 $\textit{cnt1}$ 和 $\textit{cnt2}$ 。对于 $\textit{target}$ 中的每个字符，我们计算 $\textit{cnt1}$ 中该字符出现的次数除以 $\textit{cnt2}$ 中该字符出现的次数，取最小值即可。

时间复杂度 $O(n + m)$ ，空间复杂度 $O(|\Sigma|)$ 。其中 $n$ 和 $m$ 分别是字符串 $\textit{s}$ 和 $\textit{target}$ 的长度。而 $|\Sigma|$ 是字符集的大小，本题中 $|\Sigma|=26$ 。

1

2

3

4

5

6

class Solution:
    def rearrangeCharacters(self, s: str, target: str) -> int:
        cnt1 = Counter(s)
        cnt2 = Counter(target)
        return min(cnt1[c] // v for c, v in cnt2.items())

speed

复杂度分析

指标	值
时间	complexity is O(n + m) where n is the length of s and m is the length of target due to single pass frequency counting. Space complexity is O(1) in practice since there are at most 26 lowercase letters stored in hash tables.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Asks if frequency counting is necessary for each character or can be optimized.
question_mark
Wants confirmation that letters cannot be reused across target copies.
question_mark
Checks understanding of hash table operations for string counting.

warning

常见陷阱

外企场景

error
Forgetting to take the minimum across all character counts in target.
error
Attempting to reuse letters from s for multiple target copies.
error
Not accounting for characters in target that do not exist in s.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Instead of lowercase letters, compute copies for uppercase or mixed-case target strings.
arrow_right_alt
Determine maximum copies when s can contain non-alphabetic characters that should be ignored.
arrow_right_alt
Compute copies when target has repeating letters with different frequencies.

help

常见问题

外企场景

继续练习

#2284 最多单词数的发件人 #2283 判断一个数的数字计数是否等于数位的值 #2351 第一个出现两次的字母