Submission #55822676

---

Source Code Expand

import itertools

def main():
    n, k = map(int, input().split())
    s = input()

    a = [ord(ch) - ord('a') for ch in s]
    a.sort()
    ans = 0

    while True:
        ok = True
        for i in range(n - k + 1):
            flag = True
            for j in range(k):
                if a[i + j] != a[i + k - 1 - j]:
                    flag = False
                    break
            if flag:
                ok = False
                break
        if ok:
            ans += 1
        if not next_permutation(a):
            break

    print(ans)

def next_permutation(seq):
    """
    Transform list into the next permutation.
    Return False if there is no next permutation.
    """
    # Find non-increasing suffix
    i = len(seq) - 1
    while i > 0 and seq[i - 1] >= seq[i]:
        i -= 1
    if i <= 0:
        return False

    # Find successor to pivot
    j = len(seq) - 1
    while seq[j] <= seq[i - 1]:
        j -= 1
    seq[i - 1], seq[j] = seq[j], seq[i - 1]

    # Reverse suffix
    seq[i:] = seq[i:][::-1]
    return True

if __name__ == "__main__":
    main()

Submission Info

Judge Result