3138. Minimum Length of Anagram Concatenation
Description
You are given a string s
, which is known to be a concatenation of anagrams of some string t
.
Return the minimum possible length of the string t
.
An anagram is formed by rearranging the letters of a string. For example, "aab", "aba", and, "baa" are anagrams of "aab".
Example 1:
Input: s = "abba"
Output: 2
Explanation:
One possible string t
could be "ba"
.
Example 2:
Input: s = "cdef"
Output: 4
Explanation:
One possible string t
could be "cdef"
, notice that t
can be equal to s
.
Constraints:
1 <= s.length <= 105
s
consist only of lowercase English letters.
Solutions
Solution 1: Enumeration
Based on the problem description, the length of string $\textit{t}$ must be a factor of the length of string $\textit{s}$. We can enumerate the length $k$ of string $\textit{t}$ from small to large, and then check if it meets the requirements of the problem. If it does, we return. Thus, the problem is transformed into how to check whether the length $k$ of string $\textit{t}$ meets the requirements.
First, we count the occurrence of each character in string $\textit{s}$ and record it in an array or hash table $\textit{cnt}$.
Next, we define a function $\textit{check}(k)$ to check whether the length $k$ of string $\textit{t}$ meets the requirements. We can traverse string $\textit{s}$, taking a substring of length $k$ each time, and then count the occurrence of each character. If the occurrence of each character multiplied by $\frac{n}{k}$ does not equal the value in $\textit{cnt}$, then return $\textit{false}$. If all checks pass by the end of the traversal, return $\textit{true}$.
The time complexity is $O(n \times A)$, where $n$ is the length of string $\textit{s}$, and $A$ is the number of factors of $n$. The space complexity is $O(|\Sigma|)$, where $\Sigma$ is the character set, which in this case is the set of lowercase letters.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
|