Minimum Length of Anagram Concatenation — Problem & Solution
Minimum Length of Anagram Concatenation solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Minimum Length of Anagram Concatenation is a medium coding problem on strings, hash table and counting, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Strings, Hash Table, Counting
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given a string s that is known to be a concatenation of anagrams of some string t — that is, s can be cut into consecutive pieces, each a rearrangement of t.
Return the minimum possible length of t.
Example 1
Input: s = "abba"
Output: 2
Explanation: `t = "ab"` works: `s` is `ab` + `ba`.
Example 2
Input: s = "cdef"
Output: 4
Explanation: No shorter `t` works, so `t` is `s` itself.
Example 3
Input: s = "abcbcacabbac"
Output: 3
Explanation: The pieces `abc`, `bca`, `cab`, `bac` are all anagrams of `abc`.
Constraints
1 <= s.length <= 10^5s consists only of lowercase English letters
Hints for Minimum Length of Anagram Concatenation
Hint 1
If
thas lengthd, every piece has lengthd, sodmust dividen = s.length.Hint 2
For a candidate
d, alln / dpieces must have the same letter counts as the first piece.Hint 3
Try the divisors of
nin increasing order and return the first that passes. A number up to 10^5 has at most 128 divisors, and each check is O(n).
How to solve Minimum Length of Anagram Concatenation
The length of t must divide n, and a divisor d works exactly when all aligned pieces of length d share one letter multiset. Testing divisors from the smallest up finds the minimum.
Approach
- For each
dfrom 1 tonwithn % d == 0: - Count the letters of
s[0..d - 1]. - For every later piece
s[i..i + d - 1](i = d, 2d, …), count its letters and compare with the first piece. - Return the first
dwhere all pieces match (d = nalways does).
Why it works
If s is a concatenation of anagrams of t, the pieces are the aligned blocks of length |t|, so |t| divides n and every block has t's letter counts — which are those of the first block. Conversely, if all aligned blocks share the first block's counts, t can be taken as the first block.
Complexity
- Time —
O(n · σ(n)) where σ(n) is the number of divisors (≤ 128 for n ≤ 10^5) - Space —
O(1) (26 counters)
Pitfalls
- The pieces are consecutive and aligned — any rearrangement of the whole string is not allowed.
- Testing only lengths that divide
nis required; other lengths cannot tiles.
Reference solution
Python
def minAnagramLength(s: str) -> int:
n = len(s)
for d in range(1, n + 1):
if n % d:
continue
first = [0] * 26
for c in s[:d]:
first[ord(c) - 97] += 1
ok = True
for i in range(d, n, d):
cnt = [0] * 26
for c in s[i:i + d]:
cnt[ord(c) - 97] += 1
if cnt != first:
ok = False
break
if ok:
return d
return nJava
public static int minAnagramLength(String s) {
int n = s.length();
for (int d = 1; d <= n; d++) {
if (n % d != 0) continue;
int[] first = new int[26];
for (int a = 0; a < d; a++) first[s.charAt(a) - 'a']++;
boolean ok = true;
for (int i = d; i < n && ok; i += d) {
int[] cnt = new int[26];
for (int b = i; b < i + d; b++) cnt[s.charAt(b) - 'a']++;
if (!Arrays.equals(cnt, first)) ok = false;
}
if (ok) return d;
}
return n;
}C++
int minAnagramLength(string s) {
int n = s.size();
for (int d = 1; d <= n; d++) {
if (n % d != 0) continue;
array<int, 26> first{};
for (int a = 0; a < d; a++) first[s[a] - 'a']++;
bool ok = true;
for (int i = d; i < n && ok; i += d) {
array<int, 26> cnt{};
for (int b = i; b < i + d; b++) cnt[s[b] - 'a']++;
if (cnt != first) ok = false;
}
if (ok) return d;
}
return n;
}JavaScript
var minAnagramLength = function(s) {
var n = s.length;
for (var d = 1; d <= n; d++) {
if (n % d !== 0) continue;
var first = new Array(26).fill(0);
for (var a = 0; a < d; a++) first[s.charCodeAt(a) - 97]++;
var ok = true;
for (var i = d; i < n && ok; i += d) {
var cnt = new Array(26).fill(0);
for (var b = i; b < i + d; b++) cnt[s.charCodeAt(b) - 97]++;
for (var c = 0; c < 26; c++) if (cnt[c] !== first[c]) { ok = false; break; }
}
if (ok) return d;
}
return n;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Hashing: Hash Maps and Hash Sets