We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Length of Anagram Concatenation

Number: 3395

Difficulty: Medium

Paid? No

Companies: Turing

Problem Description

Given a string s that is formed by concatenating several anagrams of an unknown string t, determine the minimum possible length of t.

Key Insights

  • s is a concatenation of copies (reordered as anagrams) of t.
  • For every letter that appears in s, its total frequency is a multiple of its frequency in t.
  • Let x be the number of copies (chunks) in s, then for every letter c in s, frequency f(c) = (frequency in t) * x.
  • To minimize the length of t, we need to maximize x, which must be a common divisor of all letter frequencies in s.
  • Thus, the maximal x equals the greatest common divisor (gcd) of all nonzero frequency counts.
  • The length of t is then computed as s.length / gcd.

Space and Time Complexity

Time Complexity: O(n) where n is the length of s (to count frequencies and compute gcd over a constant number of characters).
Space Complexity: O(1) since we only store frequency data for 26 possible lowercase letters.

Solution

We first count the frequency of each character in s using a hash table (or a fixed-size array of length 26). Next, we compute the gcd of all nonzero letter counts; this gcd represents the maximum number of anagram copies that can form s. The minimum possible length of t is then (s.length divided by this gcd). This approach leverages the fact that t's letter frequencies are scaled down versions of s's frequencies by the factor x (the number of chunks).

Code Solutions

# Function to compute the greatest common divisor (gcd) of two numbers
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

# Main function to compute the minimum length of t
def minLengthAnagramConcatenation(s: str) -> int:
    # Create an array for 26 lowercase letters
    freq = [0] * 26
    
    # Count frequency for each character in s
    for char in s:
        freq[ord(char) - ord('a')] += 1
        
    # Initialize gcd with a value of 0
    current_gcd = 0
    # Compute gcd for all non-zero frequency counts
    for count in freq:
        if count > 0:
            if current_gcd == 0:
                current_gcd = count
            else:
                current_gcd = gcd(current_gcd, count)
    
    # The answer is the length of s divided by the gcd of frequency counts
    return len(s) // current_gcd

# Example usage:
if __name__ == "__main__":
    print(minLengthAnagramConcatenation("abba"))        # Expected output: 2
    print(minLengthAnagramConcatenation("cdef"))        # Expected output: 4
    print(minLengthAnagramConcatenation("abcbcacabbaccba"))  # Expected output: 3
← Back to All Questions