Minimum length of anagram concatenation

Hash Table String Counting

39.8% acceptance

Feb 24, 2026

201

104

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

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn min_anagram_length(s: String) -> i32 {
    let n = s.len();
    let s = s.as_bytes();
    // Try divisors d in increasing order
    let freq_of_block = |start: usize, len: usize| -> [i32; 26] {
      let mut f = [0i32; 26];
      for i in 0..len {
        f[(s[start + i] - b'a') as usize] += 1;
      }
      f
    };
    'outer: for d in 1..=n {
      if n % d != 0 { continue; }
      let blocks = n / d;
      let base = freq_of_block(0, d);
      for b in 1..blocks {
        if freq_of_block(b * d, d) != base {
          continue 'outer;
        }
      }
      return d as i32;
    }
    n as i32
  }
}