Minimum Length of Anagram Concatenation - Solution & Explanation
Problem Statement
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 <= 105sconsist only of lowercase English letters.
Approach Overview
Problem Overview: You are given a string s. The string is formed by concatenating multiple substrings that are all anagrams of the same base string. Your task is to compute the minimum possible length of that base string.
The key observation: if a base string t of length k exists, then s must be split into n / k segments. Every segment must contain the same character frequency as t, just in a different order.
Approach 1: Frequency Analysis and GCD Method (O(n) time, O(1) space)
This approach relies on counting how many times each character appears in the entire string. Suppose character c appears count[c] times. If the string is composed of m anagram blocks, then the base string must contain count[c] / m occurrences of that character. For this to work, m must divide every character count.
Compute the greatest common divisor (GCD) of all character frequencies. That GCD represents the maximum number of identical anagram blocks the string can be split into. The minimum base string length becomes the sum of count[c] / gcd for all characters. Implementation uses a simple frequency array or hash map from Hash Table counting combined with a GCD calculation.
This works because each block must share identical frequency proportions. By normalizing counts with the GCD, you derive the smallest possible frequency profile that can repeat to generate the entire string.
Approach 2: Divisibility and Modular Arithmetic Analysis (O(n * d) time, O(1) space)
This method explicitly tests candidate base lengths. Let n be the length of the string. Any valid base length must divide n. For each divisor k, treat the first k characters as the frequency template. Then iterate through the string in blocks of size k, counting characters and checking if each block is an anagram of the template.
Character frequency comparisons can be implemented with arrays or counters from Counting. If all segments match, k is a valid answer. The smallest valid k is the minimum base length.
This approach is more explicit and easier to reason about during debugging. However, it performs repeated scans of the string and therefore runs slower than the GCD trick in worst cases.
Recommended for interviews: The GCD-based frequency analysis is the optimal approach and runs in O(n). Interviewers often expect you to recognize that anagram blocks imply proportional frequency counts across the entire string. Showing the divisor-check method first demonstrates clear reasoning, but the GCD insight shows stronger algorithmic intuition.
Approach 1: Frequency Analysis and GCD Method
This approach involves calculating the frequency of each character in the string s. By computing the greatest common divisor (GCD) of these frequencies, we can determine the minimum length of the original string t, because t should be such that each anagram formed from it can be repeated equal times to form s. The GCD gives us the maximum number of times the anagram can be repeated evenly across all character types.
We utilize the Python Counter to calculate the frequency of each character in s. Using the math.gcd function, we iteratively calculate the GCD of all character frequencies. This gives us the smallest possible length of t.
Code
Python
JavaScript
C++
Java
C#
Complexity
Time Complexity: O(n), where n is the length of the string s due to character counting.
Space Complexity: O(1), assuming only a constant number of English lowercase characters.
Approach 2: Divisibility and Modular Arithmetic Analysis
In this approach, we analyze how different counts of characters can be evenly divided to possibly rearrange into equal-sized parts forming the string s. This involves checking divisibility conditions and if all the character counts align to a common modularity that suggests a potential original t length. Essentially, we check if a string part can be divided in a way where each anagram fit the same pattern.
In this Python code, we calculate the maximum divisor k of a string that satisfies a condition where character frequencies modulo k equal zero, indicating each character fits perfectly into parts of size k. This is verified iteratively up to the length of s, providing our minimum t length.
Code
Python
JavaScript
Complexity
Time Complexity: O(n * sqrt(n)) due to divisibility checks for each divisor.
Space Complexity: O(1), as additional storage is minimal.
Approach 3: Enumeration
Based on the problem description, the length of string t must be a factor of the length of string s. We can enumerate the length k of string 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 t meets the requirements.
First, we count the occurrence of each character in string s and record it in an array or hash table cnt.
Next, we define a function check(k) to check whether the length k of string t meets the requirements. We can traverse string 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 cnt, then return false. If all checks pass by the end of the traversal, return true.
The time complexity is O(n times A), where n is the length of string 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.
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Frequency Analysis and GCD Method | Time Complexity: O(n), where n is the length of the string Space Complexity: O(1), assuming only a constant number of English lowercase characters. |
| Divisibility and Modular Arithmetic Analysis | Time Complexity: O(n * sqrt(n)) due to divisibility checks for each divisor. Space Complexity: O(1), as additional storage is minimal. |
| Enumeration | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Frequency Analysis and GCD Method | O(n) | O(1) | Best general solution. Uses global frequency counts to compute the minimal base pattern directly. |
| Divisibility and Modular Arithmetic Analysis | O(n * d) | O(1) | Useful for reasoning or debugging. Explicitly checks each valid segment length divisor. |
Video Solution
3138. Minimum Length of Anagram Concatenation | Divisors & Factors | Hash Map • Aryan Mittal • 4,753 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Minimum Length of Anagram Concatenation easy or hard?
Minimum Length of Anagram Concatenation Python/Java solution
How to solve Minimum Length of Anagram Concatenation in O(n)?
What is the best approach for Minimum Length of Anagram Concatenation?
Is Minimum Length of Anagram Concatenation asked at Google/Amazon/Meta?
What data structure is used in Minimum Length of Anagram Concatenation?
What is the time complexity of Minimum Length of Anagram Concatenation?
Ready to solve this problem?
Practice Minimum Length of Anagram Concatenation with our built-in code editor and test cases.
Practice on FleetCodeTable of Contents
Practice this problem
Open in Editor