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

来源第 425 场周赛 Q2难度中等分数1513

题目描述

给你两个字符串 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 互为字母异位词。

解法

方法一：哈希表

思考

把 \(s\) 与 \(t\) 都切成 \(k\) 段等长块，问块的多重集是否相同。\(n \le 2 \times 10^5\)，用计数比较即可。

对 \(s\) 的每块 \(+1\)、对 \(t\) 的每块 \(-1\)，最后计数全为 \(0\) 则可以重排得到 \(t\)。

输入已保证字母总频次相同，故只需比较分块后的多重集。

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

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

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

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

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

Python3JavaC++GoTypeScript

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())

class Solution {
    public boolean isPossibleToRearrange(String s, String t, int k) {
        Map<String, Integer> cnt = new HashMap<>(k);
        int n = s.length();
        int m = n / k;
        for (int i = 0; i < n; i += m) {
            cnt.merge(s.substring(i, i + m), 1, Integer::sum);
            cnt.merge(t.substring(i, i + m), -1, Integer::sum);
        }
        for (int v : cnt.values()) {
            if (v != 0) {
                return false;
            }
        }
        return true;
    }
}

class Solution {
public:
    bool isPossibleToRearrange(string s, string t, int k) {
        unordered_map<string, int> cnt;
        int n = s.size();
        int m = n / k;
        for (int i = 0; i < n; i += m) {
            cnt[s.substr(i, m)]++;
            cnt[t.substr(i, m)]--;
        }
        for (auto& [_, v] : cnt) {
            if (v) {
                return false;
            }
        }
        return true;
    }
};

func isPossibleToRearrange(s string, t string, k int) bool {
    n := len(s)
    m := n / k
    cnt := map[string]int{}
    for i := 0; i < n; i += m {
        cnt[s[i:i+m]]++
        cnt[t[i:i+m]]--
    }
    for _, v := range cnt {
        if v != 0 {
            return false
        }
    }
    return true
}

function isPossibleToRearrange(s: string, t: string, k: number): boolean {
    const cnt: Record<string, number> = {};
    const n = s.length;
    const m = Math.floor(n / k);
    for (let i = 0; i < n; i += m) {
        const a = s.slice(i, i + m);
        cnt[a] = (cnt[a] || 0) + 1;
        const b = t.slice(i, i + m);
        cnt[b] = (cnt[b] || 0) - 1;
    }
    return Object.values(cnt).every(x => x === 0);
}

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

题目描述

解法

方法一：哈希表

评论