Necklace Assembly (Codeforces 1367E)
Tags: Greedy, number theory

The store sells $$$n$$$ beads. The color of each bead is described by a lowercase letter of the English alphabet ("a"–"z"). You want to buy some beads to assemble a necklace from them.A necklace is a set of beads connected in a circle.For example, if the store sells beads "a", "b", "c", "a", "c", "c", then you can assemble the following necklaces (these are not all possible options):  And the following necklaces cannot be assembled from beads sold in the store:  The first necklace cannot be assembled because it has three beads "a" (of the two available). The second necklace cannot be assembled because it contains a bead "d", which is not sold in the store. We call a necklace $$$k$$$-beautiful if, when it is turned clockwise by $$$k$$$ beads, the necklace remains unchanged. For example, here is a sequence of three turns of a necklace.    As you can see, this necklace is, for example, $$$3$$$-beautiful, $$$6$$$-beautiful, $$$9$$$-beautiful, and so on, but it is not $$$1$$$-beautiful or $$$2$$$-beautiful.In particular, a necklace of length $$$1$$$ is $$$k$$$-beautiful for any integer $$$k$$$. A necklace that consists of beads of the same color is also beautiful for any $$$k$$$.You are given the integers $$$n$$$ and $$$k$$$, and also the string $$$s$$$ containing $$$n$$$ lowercase letters of the English alphabet — each letter defines a bead in the store. You can buy any subset of beads and connect them in any order. Find the maximum length of a $$$k$$$-beautiful necklace you can assemble.

Input: The first line contains a single integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases in the test. Then $$$t$$$ test cases follow.The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n, k \le 2000$$$).The second line of each test case contains the string $$$s$$$ containing $$$n$$$ lowercase English letters — the beads in the store.It is guaranteed that the sum of $$$n$$$ for all test cases does not exceed $$$2000$$$.

Output: Output $$$t$$$ answers to the test cases. Each answer is a positive integer — the maximum length of the $$$k$$$-beautiful necklace you can assemble.

Note: The first test case is explained in the statement.In the second test case, a $$$6$$$-beautiful necklace can be assembled from all the letters.In the third test case, a $$$1000$$$-beautiful necklace can be assembled, for example, from beads "abzyo".

Sample Inputs:
6
6 3
abcbac
3 6
aaa
7 1000
abczgyo
5 4
ababa
20 10
aaebdbabdbbddaadaadc
20 5
ecbedececacbcbccbdec

Sample Outputs:
6
3
5
4
15
10

Solution (Python):
import math
import collections
t = int(input())
for _ in range(t):
    (n, k) = map(int, input().split())
    s = input()
    ctr = collections.Counter(s)
    ans = 0
    for i in range(1, n + 1):
        g = math.gcd(i, k)
        l = i // g
        cnt = sum([v // l * l for v in ctr.values()])
        if cnt >= i:
            ans = i
    print(ans)

Solution (Python):
""""""
rr = lambda : input().strip()
rri = lambda : int(rr())
rrm = lambda : [int(x) for x in rr().split()]
from sys import stdin, stdout

def sol():
    (n, k) = rrm()
    s = input().strip()
    fr = [0 for i in range(26)]
    for c in s:
        fr[ord(c) - ord('a')] += 1
    res = 1
    for i in range(1, k + 1):
        if k % i == 0:
            x = 1
            while True:
                cn = x * i
                z = 0
                for j in fr:
                    z += j // x
                if z < i:
                    break
                x += 1
            x -= 1
            res = max(res, x * i)
    print(res)
    return
T = rri()
for t in range(1, T + 1):
    ans = sol()

Solution (Python):
def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)
t = int(input())
for test in range(0, t):
    (n, k) = input().split()
    n = int(n)
    k = int(k)
    s = input()
    dic = {}
    b = []
    for i in range(0, n):
        if s[i] in dic:
            b[dic[s[i]]] += 1
        else:
            dic[s[i]] = len(b)
            b.append(1)
    kk = k
    b.sort()
    for l in range(n, 0, -1):
        k = kk % l
        if k == 0:
            print(l)
            break
        s = k * l // gcd(l, k) // k
        ll = l
        for i in range(len(b) - 1, -1, -1):
            ll -= b[i] // s * s
            if ll <= 0:
                print(l)
                break
        if ll <= 0:
            break