How do I determine the length of string t?

The length of string t must be a divisor of the length of s, and t should allow all characters of s to be split evenly into anagrams of t.

What is the key observation for solving this problem?

The key observation is that the length of t must divide the length of s. This allows for efficient checking of possible candidates for t.

What is the time complexity of this problem?

The time complexity is O(n + sqrt(n)), where n is the length of s. The O(n) comes from counting character frequencies, and O(sqrt(n)) is for finding divisors of n.

Can the length of t be equal to the length of s?

Yes, the length of t can be equal to the length of s. In such a case, the string t could be the entire string s itself if s is already a valid anagram of t.

Why is hash table used here?

Hash tables are used to count the frequency of characters in string s. This allows for quick validation of whether a divisor length can form a valid string t.

#3138

Medium

auto_awesome哈希·表·结合·string

LeetCode 题解工作台

同位字符串连接的最小长度

给你一个字符串 s ，它由某个字符串 t 和若干 t 的同位字符串连接而成。请你返回字符串 t 的最小可能长度。同位字符串指的是重新排列一个字符串的字母得到的另外一个字符串。例如，"aab"，"aba" 和 "baa" 是 "aab" 的同位字符串。示例 1：输入： s = "ab…

哈希表字符串计数

题目描述

给你一个字符串 s ，它由某个字符串 t 和若干 t 的 同位字符串 连接而成。

请你返回字符串 t 的最小可能长度。

同位字符串 指的是重新排列一个字符串的字母得到的另外一个字符串。例如，"aab"，"aba" 和 "baa" 是 "aab" 的同位字符串。

示例 1：

输入：s = "abba"

输出：2

解释：

一个可能的字符串 t 为 "ba" 。

示例 2：

输入：s = "cdef"

输出：4

解释：

一个可能的字符串 t 为 "cdef" ，注意 t 可能等于 s 。

示例 3：

输入：s = "abcbcacabbaccba"

输出：3

提示：

1 <= s.length <= 10⁵
s 只包含小写英文字母。

lightbulb

解题思路

方法一：枚举

根据题目描述，字符串 $\textit{t}$ 的长度一定是 $\textit{s}$ 的长度的因子，我们可以从小到大枚举字符串 $\textit{t}$ 的长度 $k$ ，然后检查是否满足题目要求，如果满足则返回。因此，问题转化为如何检查字符串 $\textit{t}$ 的长度 $k$ 是否满足题目要求。

我们首先统计字符串 $\textit{s}$ 中每个字符出现的次数，记录在数组或哈希表 $\textit{cnt}$ 中。

然后，我们定义一个函数 $\textit{check}(k)$ ，用来检查字符串 $\textit{t}$ 的长度 $k$ 是否满足题目要求。我们可以遍历字符串 $\textit{s}$ ，每次取长度为 $k$ 的子串，然后统计每个字符出现的次数，如果每个字符出现的次数乘以 $\frac{n}{k}$ 不等于 $\textit{cnt}$ 中的值，则返回 $\textit{false}$ 。遍历结束，如果都满足，则返回 $\textit{true}$ 。

时间复杂度 $O(n \times A)$ ，其中 $n$ 是字符串 $\textit{s}$ 的长度，而 $A$ 是 $n$ 的因子个数。空间复杂度 $O(|\Sigma|)$ ，其中 $\Sigma$ 是字符集，本题中为小写字母集合。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

class Solution:
    def minAnagramLength(self, s: str) -> int:
        def check(k: int) -> bool:
            for i in range(0, n, k):
                cnt1 = Counter(s[i : i + k])
                for c, v in cnt.items():
                    if cnt1[c] * (n // k) != v:
                        return False
            return True

        cnt = Counter(s)
        n = len(s)
        for i in range(1, n + 1):
            if n % i == 0 and check(i):
                return i

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
The candidate effectively uses hash tables for counting characters.
question_mark
The candidate recognizes that the answer is a divisor of s.length.
question_mark
The candidate efficiently checks possible divisors without unnecessary computation.

warning

常见陷阱

外企场景

error
Failing to recognize that the length of t must be a divisor of the length of s.
error
Overcomplicating the problem by checking all possible substrings of s instead of focusing on divisors.
error
Incorrectly counting character frequencies or not checking for even division of characters.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Instead of a string of lowercase letters, consider a string with uppercase or mixed case characters.
arrow_right_alt
Introduce different constraints, like restricting the number of anagram groups.
arrow_right_alt
Allow t to be longer or shorter and adjust the problem accordingly.

help

常见问题

外企场景

继续练习

#3137 K 周期字符串需要的最少操作次数 #3144 分割字符频率相等的最少子字符串 #3085 成为 K 特殊字符串需要删除的最少字符数