3138. Minimum Length of Anagram Concatenation LeetCode Solution

Last updated: March 6, 2025

In this guide, you will get 3138. Minimum Length of Anagram Concatenation LeetCode Solution with the best time and space complexity. The solution to Minimum Length of Anagram Concatenation problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Minimum Length of Anagram Concatenation solution in C++
Minimum Length of Anagram Concatenation solution in Java
Minimum Length of Anagram Concatenation solution in Python
Additional Resources

3138. Minimum Length of Anagram Concatenation LeetCode Solution image

Problem Statement of Minimum Length of Anagram Concatenation

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

Example 1:

Input: s = “abba”
Output: 2
Explanation:
One possible string t could be “ba”.

Example 2:

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 <= 105
s consist only of lowercase English letters.

Complexity Analysis

Time Complexity: O(n\sqrt{n})
Space Complexity: O(26) = O(1)

3138. Minimum Length of Anagram Concatenation LeetCode Solution in C++

class Solution {
 public:
  int minAnagramLength(string s) {
    const int n = s.length();
    for (int k = 1; k <= n; ++k)
      if (n % k == 0 && canFormAnagram(s, k))
        return k;
    return n;
  }

 private:
  // Returns true if we can concatenate an anagram of length k to s.
  bool canFormAnagram(const string& s, int k) {
    const int n = s.length();
    vector<int> anagramCount(26);
    vector<int> runningCount(26);
    for (int i = 0; i < k; ++i)
      ++anagramCount[s[i] - 'a'];
    for (int i = k; i < n; ++i) {
      ++runningCount[s[i] - 'a'];
      if (i % k == k - 1) {
        if (runningCount != anagramCount)
          return false;
        fill(runningCount.begin(), runningCount.end(), 0);
      }
    }
    return true;
  }
};
/* code provided by PROGIEZ */

3138. Minimum Length of Anagram Concatenation LeetCode Solution in Java

class Solution {
  public int minAnagramLength(String s) {
    final int n = s.length();
    for (int k = 1; k <= n; ++k)
      if (n % k == 0 && canFormAnagram(s, k))
        return k;
    return n;
  }

  // Returns true if we can concatenate an anagram of length k to s.
  private boolean canFormAnagram(String s, int k) {
    final int n = s.length();
    int[] anagramCount = new int[26];
    int[] runningCount = new int[26];
    for (int i = 0; i < k; ++i)
      ++anagramCount[s.charAt(i) - 'a'];
    for (int i = k; i < n; ++i) {
      ++runningCount[s.charAt(i) - 'a'];
      if (i % k == k - 1) {
        if (!Arrays.equals(runningCount, anagramCount))
          return false;
        Arrays.fill(runningCount, 0);
      }
    }
    return true;
  }
}
// code provided by PROGIEZ

3138. Minimum Length of Anagram Concatenation LeetCode Solution in Python

class Solution:
  def minAnagramLength(self, s: str) -> int:
    n = len(s)
    for k in range(1, n + 1):
      if n % k == 0 and self._canFormAnagram(s, k):
        return k
    return n

  def _canFormAnagram(self, s: str, k: int) -> bool:
    """Returns True if we can concatenate an anagram of length k to s."""
    anagramCount = collections.Counter(s[:k])
    return all(collections.Counter(s[i:i + k]) == anagramCount
               for i in range(k, len(s), k))
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents