Minimum Length of Anagram Concatenation

Medium
1817.

Minimum Length of Anagram Concatenation

Minimum Length of Anagram Concatenation is a medium coding problem on strings, hash table and counting, asked in Amazon and Google interviews.

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^5
  • s consists only of lowercase English letters
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @return {number}
 */
var minAnagramLength = function(s) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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^5
  • s consists only of lowercase English letters

Hints for Minimum Length of Anagram Concatenation

  1. Hint 1

    If t has length d, every piece has length d, so d must divide n = s.length.

  2. Hint 2

    For a candidate d, all n / d pieces must have the same letter counts as the first piece.

  3. Hint 3

    Try the divisors of n in 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

  1. For each d from 1 to n with n % d == 0:
  2. Count the letters of s[0..d - 1].
  3. For every later piece s[i..i + d - 1] (i = d, 2d, …), count its letters and compare with the first piece.
  4. Return the first d where all pieces match (d = n always 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 n is required; other lengths cannot tile s.

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 n

Java

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