Minimum Length of Anagram Concatenation - Practice Coding Problems

Minimum Length of Anagram Concatenation - 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".

Input & Output

Example 1 — Equal Character Frequencies

$ Input: s = "abab"

› Output: 2

💡 Note: String can be split as "ab" + "ab". Both segments are anagrams of "ab", so minimum length is 2.

Example 2 — Multiple Character Pattern

$ Input: s = "aabaab"

› Output: 3

💡 Note: String can be split as "aab" + "aab". Both segments are identical anagrams, so minimum length is 3.

Example 3 — Single Character

$ Input: s = "aaaa"

› Output: 1

💡 Note: All characters are the same, so the minimum pattern is just "a" repeated 4 times.

Constraints

1 ≤ s.length ≤ 10⁵
s consists of lowercase English letters

Visualization

Tap to expand

Understanding the Visualization

Input Analysis

String s is made of concatenated anagrams

Pattern Detection

Find minimum length that divides string into valid anagrams

Result

Return the minimum possible pattern length

Key Takeaway

🎯 Key Insight: The minimum pattern length divides all character frequencies equally

Asked in

G Google 25 M Microsoft 18 a Amazon 15

The key insight is that the minimum pattern length equals the string length divided by the GCD of all character frequencies. The optimal frequency counting approach runs in O(n) time with O(1) space, much faster than brute force O(n²).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Pattern Lengths	O(n²)	O(1)	Test every possible pattern length from 1 to n
Frequency Count with GCD	O(n + 26 log k)	O(1)	Count character frequencies and find GCD for minimum pattern

Brute Force - Try All Pattern Lengths — Algorithm Steps

Step 1: Try pattern lengths from 1 to n
Step 2: For each length, divide string into segments
Step 3: Check if all segments are anagrams
Step 4: Return first valid length

Visualization

Tap to expand

Step-by-Step Walkthrough

Try Length 1

Check if all characters are the same

Try Length 2

Check if string can be split into anagram pairs

Find Valid Length

Return first length where all segments are anagrams

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(char* s) {
    int n = strlen(s);
    
    for (int length = 1; length <= n; length++) {
        if (n % length != 0) continue;
        
        int segments = n / length;
        int valid = 1;
        
        // Get frequency of first segment
        int firstFreq[26] = {0};
        for (int i = 0; i < length; i++) {
            firstFreq[s[i] - 'a']++;
        }
        
        // Compare all other segments
        for (int seg = 1; seg < segments; seg++) {
            int segFreq[26] = {0};
            for (int i = seg * length; i < (seg + 1) * length; i++) {
                segFreq[s[i] - 'a']++;
            }
            
            for (int i = 0; i < 26; i++) {
                if (segFreq[i] != firstFreq[i]) {
                    valid = 0;
                    break;
                }
            }
            
            if (!valid) break;
        }
        
        if (valid) return length;
    }
    
    return n;
}

int main() {
    char s[100001];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    
    int result = solution(s);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

For each of n possible lengths, we check n characters to verify anagrams

⚠ Quadratic Growth

Space Complexity

O(1)

Only using fixed-size frequency arrays for character counting

✓ Linear Space

33.0K Views

Medium Frequency

~15 min Avg. Time

845 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Pattern Lengths — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler