Minimum Length of Anagram Concatenation
MedPrompt
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.
Example 2:
Input: s = "abcbcacabbaccba"
Output: 3
Constraints:
1 <= s.length <= 105sconsist only of lowercase English letters.
Approaches
3 approaches with complexity analysis and trade-offs.
A straightforward approach is to test every possible length k for the string t. Since s is a concatenation of anagrams of t, the length of t, k, must be a divisor of the length of s, n. We can iterate through all divisors of n from smallest to largest. For each potential length k, we verify if s can be partitioned into n/k segments, all of which are anagrams of the first segment s[0...k-1]. Anagram checking is done by sorting each segment and comparing it to the sorted version of the first segment.
Algorithm
- The fundamental observation is that if
sis a concatenation of anagrams of a stringtof lengthk, thenkmust be a divisor of the length ofs, let's call itn. - This approach iterates through all possible lengths
kthat are divisors ofn. - To check if two strings are anagrams, we can sort their characters. If the sorted strings are equal, they are anagrams.
- The algorithm is as follows:
- Find all divisors of
n = s.length(). - Sort the divisors in ascending order.
- For each divisor
k: a. Take the first substring of lengthk,s.substring(0, k). Sort its characters to create a canonical representation,canonical_t. b. Iterate through the rest of the string in chunks of sizek. c. For each chunk, sort its characters and compare it withcanonical_t. d. If any chunk's sorted version doesn't matchcanonical_t, thenkis not a valid length. We break and try the next larger divisor. e. If all chunks match, we have found the smallest possible length fort. We returnk.
- Find all divisors of
Walkthrough
import java.util.ArrayList;import java.util.Arrays;import java.util.Collections;import java.util.List; class Solution { public int minAnagramLength(String s) { int n = s.length(); List<Integer> divisors = findDivisors(n); Collections.sort(divisors); for (int k : divisors) { if (isPossible(s, k)) { return k; } } return n; // Should not be reached given problem constraints } private List<Integer> findDivisors(int n) { List<Integer> divisors = new ArrayList<>(); for (int i = 1; i * i <= n; i++) { if (n % i == 0) { divisors.add(i); if (i * i != n) { divisors.add(n / i); } } } return divisors; } private boolean isPossible(String s, int k) { int n = s.length(); String firstSub = s.substring(0, k); char[] firstChars = firstSub.toCharArray(); Arrays.sort(firstChars); String sortedFirst = new String(firstChars); for (int i = k; i < n; i += k) { String currentSub = s.substring(i, i + k); char[] currentChars = currentSub.toCharArray(); Arrays.sort(currentChars); String sortedCurrent = new String(currentChars); if (!sortedFirst.equals(sortedCurrent)) { return false; } } return true; }}Complexity
Time
O(d(n) * n log n). Finding divisors takes `O(sqrt(n))`. For each of the `d(n)` divisors, we perform a check. The check for a given length `k` involves `n/k` substrings. Sorting each substring of length `k` takes `O(k log k)`. Thus, the check costs `O((n/k) * k log k) = O(n log k)`. The total complexity is dominated by checks for larger `k`, approaching `O(d(n) * n log n)`.
Space
O(d(n) + n). `O(d(n))` to store the divisors, where `d(n)` is the number of divisors of `n`. Additionally, `O(k)` space is required for character arrays during sorting, which can be up to `O(n)` in the worst case.
Trade-offs
Pros
Conceptually simple and easy to follow.
Correctly identifies the minimal length by checking divisors in increasing order.
Cons
The process of creating substrings and sorting them repeatedly is computationally expensive.
Time complexity is high, making it unsuitable for large inputs as it might lead to a 'Time Limit Exceeded' error.
Solutions
Solution
class Solution {private int n;private char[] s;private int[] cnt = new int[26];public int minAnagramLength(String s) { n = s.length(); this.s = s.toCharArray(); for (int i = 0; i < n; ++i) { ++cnt[this.s[i] - 'a']; } for (int i = 1;; ++i) { if (n % i == 0 && check(i)) { return i; } } }private boolean check(int k) { for (int i = 0; i < n; i += k) { int[] cnt1 = new int[26]; for (int j = i; j < i + k; ++j) { ++cnt1[s[j] - 'a']; } for (int j = 0; j < 26; ++j) { if (cnt1[j] * (n / k) != cnt[j]) { return false; } } } return true; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.