3138. Minimum Length of Anagram Concatenation

Posted on Edited on In

3138. Minimum Length of Anagram Concatenation

Description

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:

1
2
3
4
5
6
7
Input: s = "abba"

Output: 2

Explanation:

One possible string `t` could be `"ba"`.

Example 2:

1
2
3
4
5
6
7
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 <= 10^5
  • s consist only of lowercase English letters.

Hints/Notes

  • iterate the factors

Solution

Language: C++

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
30
31
32
33
class Solution {
public:
    int minAnagramLength(string s) {
        int size = s.size();
        for (int i = 1; i <= size / 2; i++) {
            if (size % i != 0) {
                continue;
            }
            map<int, int> m;
            int j;
            for (j = 0; j < i; j++) {
                m[s[j] - 'a']++;
            }
            int ok = true;
            while(j < size) {
                map<int, int> cur;
                for (int k = j; k < j + i; k++) {
                    cur[s[k] - 'a']++;
                }
                for (auto it : m) {
                    if (it.second != cur[it.first]) {
                        ok = false;
                        break;
                    }
                }
                if (!ok) break;
                j += i;
            }
            if (ok) return i;
        }
        return size;
    }
};