What is the best approach to solve Rearrange K Substrings to Form Target String?

Split s into k equal substrings and use a hash map to track substring frequencies, then verify t can be formed using these counts.

Can this problem be solved without hash tables?

Technically yes, by generating all permutations, but it is highly inefficient; hash tables optimize frequency checking.

What should I watch out for with k and substring lengths?

Ensure s.length is divisible by k, and handle exact substring boundaries to avoid off-by-one errors.

Is sorting substrings enough to verify rearrangement?

No, sorting alone does not account for multiple identical substrings; frequency maps are required.

How does the Hash Table plus String pattern apply here?

It tracks how many times each substring occurs and ensures t can be built using these counts without unnecessary permutations.

#3365

Medium

auto_awesome哈希·表·结合·string

LeetCode 题解工作台

重排子字符串以形成目标字符串

给你两个字符串 s 和 t （它们互为字母异位词），以及一个整数 k 。你的任务是判断是否可以将字符串 s 分割成 k 个等长的子字符串，然后重新排列这些子字符串，并以任意顺序连接它们，使得最终得到的新字符串与给定的字符串 t 相匹配。如果可以做到，返回 true ；否则，返回 false 。 …

哈希表字符串排序

题目描述

给你两个字符串 s 和 t（它们互为字母异位词），以及一个整数 k。

你的任务是判断是否可以将字符串 s 分割成 k 个等长的子字符串，然后重新排列这些子字符串，并以任意顺序连接它们，使得最终得到的新字符串与给定的字符串 t 相匹配。

如果可以做到，返回 true；否则，返回 false。

字母异位词 是指由另一个单词或短语的所有字母重新排列形成的单词或短语，使用所有原始字母恰好一次。

子字符串 是字符串中的一个连续非空字符序列。

示例 1：

输入： s = "abcd", t = "cdab", k = 2

输出： true

解释：

将 s 分割成 2 个长度为 2 的子字符串：["ab", "cd"]。
重新排列这些子字符串为 ["cd", "ab"]，然后连接它们得到 "cdab"，与 t 相匹配。

示例 2：

输入： s = "aabbcc", t = "bbaacc", k = 3

输出： true

解释：

将 s 分割成 3 个长度为 2 的子字符串：["aa", "bb", "cc"]。
重新排列这些子字符串为 ["bb", "aa", "cc"]，然后连接它们得到 "bbaacc"，与 t 相匹配。

示例 3：

输入： s = "aabbcc", t = "bbaacc", k = 2

输出： false

解释：

将 s 分割成 2 个长度为 3 的子字符串：["aab", "bcc"]。
这些子字符串无法重新排列形成 t = "bbaacc"，所以输出 false。

提示：

1 <= s.length == t.length <= 2 * 10⁵
1 <= k <= s.length
s.length 能被 k 整除。
s 和 t 仅由小写英文字母组成。
输入保证 s 和 t 互为字母异位词。

lightbulb

解题思路

方法一：哈希表

我们记字符串 $s$ 的长度为 $n$ ，那么每个子字符串的长度为 $m = n / k$ 。

用一个哈希表 $\textit{cnt}$ 记录每个长度为 $m$ 的子字符串在字符串 $s$ 中出现的次数与在字符串 $t$ 中出现的次数之差。

遍历字符串 $s$ ，每次取出长度为 $m$ 的子字符串，更新哈希表 $\textit{cnt}$ 。

最后判断哈希表 $\textit{cnt}$ 中的所有值是否都为 $0$ 。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为字符串 $s$ 的长度。

1

2

3

4

5

6

7

8

9

10

class Solution:
    def isPossibleToRearrange(self, s: str, t: str, k: int) -> bool:
        cnt = Counter()
        n = len(s)
        m = n // k
        for i in range(0, n, m):
            cnt[s[i : i + m]] += 1
            cnt[t[i : i + m]] -= 1
        return all(v == 0 for v in cnt.values())

speed

复杂度分析

指标	值
时间	complexity depends on the substring splitting and frequency map operations, roughly O(n) where n is the length of s. Space complexity is O(k) for storing substring counts in the hash map, assuming substring length is constant relative to n.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Emphasize handling exact k substring partitions and potential off-by-one errors.
question_mark
Expect discussion of hash table usage to track substring frequencies efficiently.
question_mark
Be prepared to explain why naive permutation checks would be inefficient for larger n.

warning

常见陷阱

外企场景

error
Forgetting to check that s.length is divisible by k, causing incorrect substring sizes.
error
Using a simple sort of substrings without counting frequencies can miss valid rearrangements.
error
Failing to decrement the hash map counts properly leads to false positives when matching t.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Allowing k to be variable instead of fixed, requiring dynamic substring partitioning.
arrow_right_alt
Checking if rearrangement is possible with substrings of unequal length, increasing complexity.
arrow_right_alt
Extending to multi-character alphabets or Unicode strings, affecting hash map size and performance.

help

常见问题

外企场景

继续练习

#3458 选择 K 个互不重叠的特殊子字符串 #3545 不同字符数量最多为 K 时的最少删除数 #3556 最大质数子字符串之和