Submission #55915719

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import sys
# {1,2,3} -> ... -> {3,2,1}
def next_permutation(arr, n):
  target = -1
  for i in range(n - 2, -1, -1):
    if arr[i] < arr[i + 1]:
      target = i
      break
  if target < 0:
    return False
  i = 0
  while target + i + 1 < n - i - 1:
    temp = arr[target + 1 + i]
    arr[target + 1 + i] = arr[n - 1 - i]
    arr[n - i - 1] = temp
    i += 1
  i = target + 1
  for j in range(target + 1, n):
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

import sys

# {1,2,3} -> ... -> {3,2,1}
def next_permutation(arr, n):
	target = -1
	for i in range(n - 2, -1, -1):
		if arr[i] < arr[i + 1]:
			target = i
			break
	if target < 0:
		return False

	i = 0
	while target + i + 1 < n - i - 1:
		temp = arr[target + 1 + i]
		arr[target + 1 + i] = arr[n - 1 - i]
		arr[n - i - 1] = temp
		i += 1

	i = target + 1
	for j in range(target + 1, n):
		if arr[j] > arr[target]:
			i = j
			break
	temp = arr[i]
	arr[i] = arr[target]
	arr[target] = temp
	return True

N, K = [int(x) for x in sys.stdin.readline().rstrip().split(" ")]
S = list(sys.stdin.readline().rstrip())

S = sorted(S)
count = 0

while True:
	ok = True
	for i in range(K, N + 1):
		local_ok = False
		for j in range(0, K):
			if S[i - K + j] != S[i - 1 - j]:
				local_ok = True
				break
		if not local_ok:
			ok = False
			break
	if ok:
		count += 1
	if not next_permutation(S, N):
		break

print(count)

Submission Info

Judge Result