题目描述

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

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

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

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

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

样例

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

输出： true

解释：

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

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

输出： true

解释：

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

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

输出： false

解释：

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

限制

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

算法

(哈希表) $O(n)$

1. 将字符串 $s$ 按照 $n / k$ 个一组分割开，将其存储哈希表中。
2. 再将字符串 $t$ 也按照 $n / k$ 个一组分割开，判断哈希表中是否有足够的子串匹配。

时间复杂度

• 分割并存储哈希表的时间复杂度为 $O(n)$。
• 分割并匹配的时间复杂度也为 $O(n)$。
• 故总时间复杂度为 $O(n)$。

空间复杂度

• 需要 $O(n)$ 的额外空间存储哈希表。

C++ 代码

class Solution {
public:
    bool isPossibleToRearrange(string s, string t, int k) {
        const int n = s.size();

        unordered_map<string, int> h;
        string c;

        k = n / k;

        for (int i = 0; i < n; i++) {
            c += s[i];
            if (i % k != k - 1)
                continue;

            ++h[c];
            c.clear();
        }

        for (int i = 0; i < n; i++) {
            c += t[i];
            if (i % k != k - 1)
                continue;

            if (h[c] == 0)
                return false;

            --h[c];
            c.clear();
        }

        return true;
    }
};