Minimum Length of Anagram Concatenation

Med

#2788Time: 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.2 companies

Patterns

Counting

Data structures

Hash Table String

Companies

UKG Turing

Prompt

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 <= 10⁵
s consist 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 s is a concatenation of anagrams of a string t of length k, then k must be a divisor of the length of s, let's call it n.
This approach iterates through all possible lengths k that are divisors of n.
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:
1. Find all divisors of n = s.length().
2. Sort the divisors in ascending order.
3. For each divisor k: a. Take the first substring of length k, 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 size k. c. For each chunk, sort its characters and compare it with canonical_t. d. If any chunk's sorted version doesn't match canonical_t, then k is not a valid length. We break and try the next larger divisor. e. If all chunks match, we have found the smallest possible length for t. We return k.

Walkthrough

1import java.util.ArrayList;2import java.util.Arrays;3import java.util.Collections;4import java.util.List;5 6class Solution {7    public int minAnagramLength(String s) {8        int n = s.length();9        List<Integer> divisors = findDivisors(n);10        Collections.sort(divisors);11 12        for (int k : divisors) {13            if (isPossible(s, k)) {14                return k;15            }16        }17        return n; // Should not be reached given problem constraints18    }19 20    private List<Integer> findDivisors(int n) {21        List<Integer> divisors = new ArrayList<>();22        for (int i = 1; i * i <= n; i++) {23            if (n % i == 0) {24                divisors.add(i);25                if (i * i != n) {26                    divisors.add(n / i);27                }28            }29        }30        return divisors;31    }32 33    private boolean isPossible(String s, int k) {34        int n = s.length();35        String firstSub = s.substring(0, k);36        char[] firstChars = firstSub.toCharArray();37        Arrays.sort(firstChars);38        String sortedFirst = new String(firstChars);39 40        for (int i = k; i < n; i += k) {41            String currentSub = s.substring(i, i + k);42            char[] currentChars = currentSub.toCharArray();43            Arrays.sort(currentChars);44            String sortedCurrent = new String(currentChars);45            if (!sortedFirst.equals(sortedCurrent)) {46                return false;47            }48        }49        return true;50    }51}

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.

We can optimize the anagram checking part of the previous approach. Sorting each substring is inefficient. A better way to check if two strings are anagrams is to compare their character counts. We can use an array of size 26 to store the frequency of each character. This reduces the cost of checking one block from O(k log k) to O(k), leading to a significant overall performance improvement.

Algorithm

This approach is similar to the first one but uses a more efficient method for the anagram check.
Instead of sorting, we use frequency maps (e.g., an array of size 26 for lowercase English letters) to represent the character counts of a string.
Two strings are anagrams if and only if their frequency maps are identical.
The algorithm is as follows:
1. Find all divisors of n = s.length() and sort them.
2. For each divisor k: a. Compute the frequency map of the first substring s[0...k-1]. b. Iterate through the subsequent n/k - 1 blocks of length k. c. For each block, compute its frequency map. d. Compare the current block's frequency map with the first block's map. This comparison is a constant time operation (O(26)). e. If any map differs, k is invalid. Continue to the next divisor. f. If all blocks have identical frequency maps, k is the minimal length. Return k.

Walkthrough

1import java.util.ArrayList;2import java.util.Arrays;3import java.util.Collections;4import java.util.List;5 6class Solution {7    public int minAnagramLength(String s) {8        int n = s.length();9        List<Integer> divisors = findDivisors(n);10        Collections.sort(divisors);11 12        for (int k : divisors) {13            if (isPossible(s, k)) {14                return k;15            }16        }17        return n;18    }19 20    private List<Integer> findDivisors(int n) {21        List<Integer> divisors = new ArrayList<>();22        for (int i = 1; i * i <= n; i++) {23            if (n % i == 0) {24                divisors.add(i);25                if (i * i != n) {26                    divisors.add(n / i);27                }28            }29        }30        return divisors;31    }32 33    private boolean isPossible(String s, int k) {34        int n = s.length();35        int[] firstBlockFreq = new int[26];36        for (int i = 0; i < k; i++) {37            firstBlockFreq[s.charAt(i) - 'a']++;38        }39 40        for (int i = k; i < n; i += k) {41            int[] currentBlockFreq = new int[26];42            for (int j = 0; j < k; j++) {43                currentBlockFreq[s.charAt(i + j) - 'a']++;44            }45            if (!Arrays.equals(firstBlockFreq, currentBlockFreq)) {46                return false;47            }48        }49        return true;50    }51}

Complexity

Time

O(d(n) * n). Finding divisors is `O(sqrt(n))`. For each divisor `k`, the check takes `O((n/k) * k) = O(n)`. The total time is `O(d(n) * n)`. Since `d(n)` is significantly smaller than `n` (for `n=10^5`, max `d(n)` is 128), this is a major improvement.

Space

O(d(n)). `O(d(n))` to store divisors. The frequency maps require constant space, `O(26)`.

Trade-offs

Pros

More efficient than the sorting-based approach.
Reduces the complexity of the anagram check from O(k log k) to O(k).

Cons

While better than sorting, the check for each divisor still requires iterating through the entire string, which can be inefficient if the number of divisors is large or the correct k is large.

To achieve the best performance, we can further optimize the check for each divisor. The previous approach re-calculates the frequency map for each block from scratch, which involves iterating over the block's characters. We can avoid this by pre-calculating the prefix sums of character frequencies for the entire string s. With this pre-computation, we can find the character counts of any substring in constant time. This dramatically speeds up the check for each divisor k from O(n) to O(n/k).

Algorithm

This approach optimizes the check for each divisor k by pre-calculating prefix sums of character frequencies.
A prefix sum table allows us to find the frequency map of any substring s[i...j] in O(1) time (specifically O(26)), by subtracting the prefix sums at i from the prefix sums at j+1.
The algorithm is as follows:
1. Precompute a prefix sum table prefixCounts of size (n+1) x 26. prefixCounts[i][c] stores the count of character c in s[0...i-1]. This takes O(n) time.
2. Find and sort all divisors of n.
3. For each divisor k: a. Determine the frequency map of the first block s[0...k-1] using prefixCounts[k]. This is an O(1) operation. b. Iterate through the subsequent blocks. For a block starting at index i, its frequency map is found by prefixCounts[i+k] - prefixCounts[i], also an O(1) operation. c. Compare this map with the first block's map. d. If there's a mismatch, k is invalid. e. If all blocks match, k is the answer. Return k.

Walkthrough

1import java.util.ArrayList;2import java.util.Arrays;3import java.util.Collections;4import java.util.List;5 6class Solution {7    public int minAnagramLength(String s) {8        int n = s.length();9        10        int[][] prefixCounts = new int[n + 1][26];11        for (int i = 0; i < n; i++) {12            for (int j = 0; j < 26; j++) {13                prefixCounts[i + 1][j] = prefixCounts[i][j];14            }15            prefixCounts[i + 1][s.charAt(i) - 'a']++;16        }17 18        List<Integer> divisors = findDivisors(n);19        Collections.sort(divisors);20 21        for (int k : divisors) {22            if (isPossible(n, k, prefixCounts)) {23                return k;24            }25        }26        return n;27    }28 29    private List<Integer> findDivisors(int n) {30        List<Integer> divisors = new ArrayList<>();31        for (int i = 1; i * i <= n; i++) {32            if (n % i == 0) {33                divisors.add(i);34                if (i * i != n) {35                    divisors.add(n / i);36                }37            }38        }39        return divisors;40    }41 42    private boolean isPossible(int n, int k, int[][] prefixCounts) {43        int[] firstBlockFreq = new int[26];44        for (int j = 0; j < 26; j++) {45            firstBlockFreq[j] = prefixCounts[k][j];46        }47 48        for (int i = k; i < n; i += k) {49            int[] currentBlockFreq = new int[26];50            for (int j = 0; j < 26; j++) {51                currentBlockFreq[j] = prefixCounts[i + k][j] - prefixCounts[i][j];52            }53            if (!Arrays.equals(firstBlockFreq, currentBlockFreq)) {54                return false;55            }56        }57        return true;58    }59}

Complexity

Time

O(n + σ₁(n)). The precomputation of prefix sums takes `O(n)`. The check for a given divisor `k` takes `O((n/k) * 26) = O(n/k)`. The total time for checking all divisors is `Σ_{k|n} O(n/k) = O(Σ_{k|n} n/k) = O(Σ_{d|n} d) = O(σ₁(n))`, where `σ₁(n)` is the sum of the divisors of `n`. This complexity is very efficient, roughly `O(n log log n)` for typical numbers.

Space

O(n). The prefix sum table requires `O(n * 26)` space, which simplifies to `O(n)`.

Trade-offs

Pros

Highly efficient and the optimal solution for this problem.
Reduces the check for each divisor k to O(n/k), making the total time complexity much better.

Cons

Requires additional space proportional to the input string length, which might be a concern for very large strings in memory-constrained environments.

Solutions

Solution

1class Solution {2private3  int n;4private5  char[] s;6private7  int[] cnt = new int[26];8public9  int minAnagramLength(String s) {10    n = s.length();11    this.s = s.toCharArray();12    for (int i = 0; i < n; ++i) {13      ++cnt[this.s[i] - 'a'];14    }15    for (int i = 1;; ++i) {16      if (n % i == 0 && check(i)) {17        return i;18      }19    }20  }21private22  boolean check(int k) {23    for (int i = 0; i < n; i += k) {24      int[] cnt1 = new int[26];25      for (int j = i; j < i + k; ++j) {26        ++cnt1[s[j] - 'a'];27      }28      for (int j = 0; j < 26; ++j) {29        if (cnt1[j] * (n / k) != cnt[j]) {30          return false;31        }32      }33    }34    return true;35  }36}

1class Solution {2public:3  int minAnagramLength(string s) {4    int n = s.size();5    int cnt[26]{};6    for (char c : s) {7      cnt[c - 'a']++;8    }9    auto check = [&](int k) {10      for (int i = 0; i < n; i += k) {11        int cnt1[26]{};12        for (int j = i; j < i + k; ++j) {13          cnt1[s[j] - 'a']++;14        }15        for (int j = 0; j < 26; ++j) {16          if (cnt1[j] * (n / k) != cnt[j]) {17            return false;18          }19        }20      }21      return true;22    };23    for (int i = 1;; ++i) {24      if (n % i == 0 && check(i)) {25        return i;26      }27    }28  }29};

1class Solution:2    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

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.

← Previous

Previous problem

Next problem

Solution

1class Solution {2private3  int n;4private5  char[] s;6private7  int[] cnt = new int[26];8public9  int minAnagramLength(String s) {10    n = s.length();11    this.s = s.toCharArray();12    for (int i = 0; i < n; ++i) {13      ++cnt[this.s[i] - 'a'];14    }15    for (int i = 1;; ++i) {16      if (n % i == 0 && check(i)) {17        return i;18      }19    }20  }21private22  boolean check(int k) {23    for (int i = 0; i < n; i += k) {24      int[] cnt1 = new int[26];25      for (int j = i; j < i + k; ++j) {26        ++cnt1[s[j] - 'a'];27      }28      for (int j = 0; j < 26; ++j) {29        if (cnt1[j] * (n / k) != cnt[j]) {30          return false;31        }32      }33    }34    return true;35  }36}

1class Solution {2public:3  int minAnagramLength(string s) {4    int n = s.size();5    int cnt[26]{};6    for (char c : s) {7      cnt[c - 'a']++;8    }9    auto check = [&](int k) {10      for (int i = 0; i < n; i += k) {11        int cnt1[26]{};12        for (int j = i; j < i + k; ++j) {13          cnt1[s[j] - 'a']++;14        }15        for (int j = 0; j < 26; ++j) {16          if (cnt1[j] * (n / k) != cnt[j]) {17            return false;18          }19        }20      }21      return true;22    };23    for (int i = 1;; ++i) {24      if (n % i == 0 && check(i)) {25        return i;26      }27    }28  }29};

1class Solution:2    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

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.