Skip to content

3138. Minimum Length of Anagram Concatenation

  • Time: $O(n\sqrt{n})$
  • Space: $O(26) = O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
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;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
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))