2025-06-15：重排子字符串以形成目标字符串。用go语言，给定两个字符串 s 和 t，它们是字母异位词（即包含完全相同的字符，只是顺序不同），以及一个整数 k。

你的任务是判断是否可能将 s 分成 k 个长度相等的连续子串，然后对这些子串重新排序，最终拼接成字符串 t。

如果可以实现，返回 true；否则返回 false。

1 <= s.length == t.length <= 2 * 100000。

1 <= k <= s.length。

s.length 能被 k 整除。

s 和 t 仅由小写英文字母组成。

输入保证 s 和 t 互为字母异位词。

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

输出： true。

解释：

将 s 分割成 3 个长度为 2 的子字符串：["aa", "bb", "cc"]。

重新排列这些子字符串为 ["bb", "aa", "cc"]，然后连接它们得到 "bbaacc"，与 t 相匹配。

题目来自力扣3365。

步骤描述：

1. 初始化切片：

o 创建两个长度为 k 的字符串切片 a 和 b，用于存储分割后的子字符串。这里 k 是分割的子字符串数量。

2. 计算子字符串长度：

o 计算每个子字符串的长度 n/k，其中 n 是字符串 s 和 t 的长度。这里 n 必须能被 k 整除，题目已保证这一点。

3. 分割字符串 s 和 t：

o 将字符串 s 分割为 k 个长度为 n/k 的连续子字符串，并存储到切片 a 中。

o 同样地，将字符串 t 分割为 k 个长度为 n/k 的连续子字符串，并存储到切片 b 中。

4. 排序切片：

o 对切片 a 和 b 分别进行排序。排序的目的是为了后续比较两个切片是否包含完全相同的子字符串（顺序可以不同）。

5. 比较切片：

o 比较排序后的 a 和 b 是否完全相同。如果相同，说明可以通过重新排列 s 的子字符串得到 t，返回 true；否则返回 false。

时间复杂度：

1. 分割字符串：分割 s 和 t 各需要 O(n) 时间，因为需要遍历整个字符串。

2. 排序切片：每个切片有 k 个元素，每个元素的长度为 n/k。排序的比较操作是字符串比较，最坏情况下需要 O(n/k) 时间（例如所有字符串几乎相同）。因此排序的总时间复杂度为 O(k * logk * (n/k)) = O(n logk)。

o 排序 a 和 b 的总时间为 O(n logk)。

3. 比较切片：比较两个长度为 k 的切片，每个字符串比较需要 O(n/k) 时间，因此总时间为 O(n)。

o 总时间复杂度：O(n) + O(n logk) + O(n) = O(n logk)。

额外空间复杂度：

1. 存储切片 a 和 b：每个切片存储 k 个子字符串，每个子字符串长度为 n/k，因此总空间为 O(2 * n) = O(n)。

2. 排序的额外空间：Go 的 slices.Sort 对字符串切片的排序通常需要 O(k) 的额外空间（用于存储指针或索引）。

o 总额外空间复杂度：O(n) + O(k) = O(n)（因为 k <= n）。

总结：

o 总时间复杂度：O(n logk)。

o 总额外空间复杂度：O(n)。

Go完整代码如下：

.

package main

import (
    "fmt"
    "slices"
)

func isPossibleToRearrange(s, t string, k int)bool {
    a := make([]string, 0, k) // 预分配空间
    b := make([]string, 0, k)
    n := len(s)
    k = n / k
    for i := k; i <= n; i += k {
        a = append(a, s[i-k:i])
        b = append(b, t[i-k:i])
    }
    slices.Sort(a)
    slices.Sort(b)
    return slices.Equal(a, b)
}


func main() {
    s := "aabbcc"
    t := "bbaacc"
    k := 3
    fmt.Println(isPossibleToRearrange(s,t,k))
}

Python完整代码如下：

.

# -*-coding:utf-8-*-

def is_possible_to_rearrange(s: str, t: str, k: int) -> bool:
    n = len(s)
    segment_len = n // k
    a = [s[i:i+segment_len] for i in range(0, n, segment_len)]
    b = [t[i:i+segment_len] for i in range(0, n, segment_len)]
    
    a.sort()
    b.sort()
    
    return a == b


if __name__ == "__main__":
    s = "aabbcc"
    t = "bbaacc"
    k = 3
    print(is_possible_to_rearrange(s, t, k))

·

我们相信Go语言和算法为普通开发者提供了困境的“面试利器”，并致力于分享全面的编程知识。在这里，您可以找到最新的Go语言教程、算法解析、提升面试竞争力的秘籍以及行业动态。

欢迎关注“福大规模架构师每日一题”，让 Go 语言和算法助力您的职业发展

·