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”.

Examples

Example 1

1
2
3
4
5
6
7
8


Input: s = "abba"

Output: 2

Explanation:

One possible string `t` could be `"ba"`.

Example 2

1
2
3
4
5
6
7
8
9


Input: s = "cdef"

Output: 4

Explanation:

One possible string `t` could be `"cdef"`, notice that `t` can be equal to
`s`.

Constraints

  • 1 <= s.length <= 10^5
  • s consist only of lowercase English letters.

Solution

Method 1 – GCD of Character Counts

Intuition

Since s is a concatenation of anagrams of t, the frequency of each character in s must be a multiple of its frequency in t. The minimum possible length of t is the sum of the greatest common divisors (GCD) of the counts of each character in s.

Approach

  1. Count the frequency of each character in s.
  2. Compute the GCD of all character counts.
  3. The minimum length of t is the sum of the counts of each character divided by the GCD.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
public:
    int minAnagramLength(string s) {
        vector<int> cnt(26);
        for (char c : s) cnt[c-'a']++;
        int g = 0;
        for (int x : cnt) if (x) g = gcd(g, x);
        int ans = 0;
        for (int x : cnt) if (x) ans += x / g;
        return ans;
    }
    int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

func minAnagramLength(s string) int {
    cnt := make([]int, 26)
    for _, c := range s {
        cnt[c-'a']++
    }
    g := 0
    gcd := func(a, b int) int {
        for b != 0 {
            a, b = b, a%b
        }
        return a
    }
    for _, x := range cnt {
        if x > 0 {
            if g == 0 { g = x } else { g = gcd(g, x) }
        }
    }
    ans := 0
    for _, x := range cnt {
        if x > 0 {
            ans += x / g
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    public int minAnagramLength(String s) {
        int[] cnt = new int[26];
        for (char c : s.toCharArray()) cnt[c-'a']++;
        int g = 0;
        for (int x : cnt) if (x > 0) g = gcd(g, x);
        int ans = 0;
        for (int x : cnt) if (x > 0) ans += x / g;
        return ans;
    }
    private int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    fun minAnagramLength(s: String): Int {
        val cnt = IntArray(26)
        for (c in s) cnt[c-'a']++
        var g = 0
        fun gcd(a: Int, b: Int): Int = if (b == 0) a else gcd(b, a % b)
        for (x in cnt) if (x > 0) g = if (g == 0) x else gcd(g, x)
        var ans = 0
        for (x in cnt) if (x > 0) ans += x / g
        return ans
    }
}
1
2
3
4
5
6
7

def min_anagram_length(s: str) -> int:
    from math import gcd
    from functools import reduce
    from collections import Counter
    cnt = Counter(s)
    g = reduce(gcd, cnt.values())
    return sum(x // g for x in cnt.values())
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

impl Solution {
    pub fn min_anagram_length(s: String) -> i32 {
        let mut cnt = [0; 26];
        for c in s.chars() {
            cnt[c as usize - 'a' as usize] += 1;
        }
        let mut g = 0;
        for &x in &cnt {
            if x > 0 {
                g = if g == 0 { x } else { gcd(g, x) };
            }
        }
        let mut ans = 0;
        for &x in &cnt {
            if x > 0 {
                ans += x / g;
            }
        }
        ans
    }
}
fn gcd(a: i32, b: i32) -> i32 {
    if b == 0 { a } else { gcd(b, a % b) }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    minAnagramLength(s: string): number {
        const cnt = Array(26).fill(0);
        for (const c of s) cnt[c.charCodeAt(0) - 97]++;
        let g = 0;
        const gcd = (a: number, b: number): number => b === 0 ? a : gcd(b, a % b);
        for (const x of cnt) if (x > 0) g = g === 0 ? x : gcd(g, x);
        let ans = 0;
        for (const x of cnt) if (x > 0) ans += x / g;
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of s. Counting and GCD are linear.
  • 🧺 Space complexity: O(1), for character counts.