Minimum Length of Anagram Concatenation

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.

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

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