# Minimum Length of Anagram Concatenation
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-length-of-anagram-concatenation)
Canonical: https://scaleengineer.com/dsa/problems/minimum-length-of-anagram-concatenation
**Patterns:** [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Data structures:** Hash Table, String
**Companies:** [UKG](https://scaleengineer.com/companies/ukg), [Turing](https://scaleengineer.com/companies/turing)
---
## Problem
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 <= 105`
* `s` consist only of lowercase English letters.

# Approaches
## Approach 1: Checking Divisors with Sorting
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.
**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.
**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.
### Explanation
```java
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;
    }
}
```
### 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`.

## Approach 2: Checking Divisors with Frequency Maps
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.
**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)`.
**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.
### Explanation
```java
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;
    }

    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();
        int[] firstBlockFreq = new int[26];
        for (int i = 0; i < k; i++) {
            firstBlockFreq[s.charAt(i) - 'a']++;
        }

        for (int i = k; i < n; i += k) {
            int[] currentBlockFreq = new int[26];
            for (int j = 0; j < k; j++) {
                currentBlockFreq[s.charAt(i + j) - 'a']++;
            }
            if (!Arrays.equals(firstBlockFreq, currentBlockFreq)) {
                return false;
            }
        }
        return true;
    }
}
```
### 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`.

## Approach 3: Optimized Check with Prefix Sums
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)`.
**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)`.
**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.
### Explanation
```java
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();
        
        int[][] prefixCounts = new int[n + 1][26];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < 26; j++) {
                prefixCounts[i + 1][j] = prefixCounts[i][j];
            }
            prefixCounts[i + 1][s.charAt(i) - 'a']++;
        }

        List<Integer> divisors = findDivisors(n);
        Collections.sort(divisors);

        for (int k : divisors) {
            if (isPossible(n, k, prefixCounts)) {
                return k;
            }
        }
        return n;
    }

    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(int n, int k, int[][] prefixCounts) {
        int[] firstBlockFreq = new int[26];
        for (int j = 0; j < 26; j++) {
            firstBlockFreq[j] = prefixCounts[k][j];
        }

        for (int i = k; i < n; i += k) {
            int[] currentBlockFreq = new int[26];
            for (int j = 0; j < 26; j++) {
                currentBlockFreq[j] = prefixCounts[i + k][j] - prefixCounts[i][j];
            }
            if (!Arrays.equals(firstBlockFreq, currentBlockFreq)) {
                return false;
            }
        }
        return true;
    }
}
```
### 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`.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minAnagramLength(string s) {
    int n = s.size();
    int cnt[26]{};
    for (char c : s) {
      cnt[c - 'a']++;
    }
    auto check = [&](int k) {
      for (int i = 0; i < n; i += k) {
        int cnt1[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;
    };
    for (int i = 1;; ++i) {
      if (n % i == 0 && check(i)) {
        return i;
      }
    }
  }
};

```

### Python

```python
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

```