Problem:


Score : 1300 points

Problem Statement

Takahashi has a string S of length N consisting of lowercase English letters.
On this string, he will perform the following operation K times:

Let T be the string obtained by reversing S, and U be the string obtained by concatenating S and T in this order.

Let S' be some contiguous substring of U with length N, and replace S with S'.

Among the strings that can be the string S after the K operations, find the lexicographically smallest possible one.

Constraints

1 \leq N \leq 5000

1 \leq K \leq 10^9

|S|=N

S consists of lowercase English letters.

Input

Input is given from Standard Input in the following format:

N K
S

Output

Print the lexicographically smallest possible string that can be the string S after the K operations.

Sample Input 1

5 1
bacba

Sample Output 1

aabca

When S=bacba, T=abcab, U=bacbaabcab, and the optimal choice of S' is S'=aabca.

Sample Input 2

10 2
bbaabbbaab

Sample Output 2

aaaabbaabb



Sample input:
5 1
bacba


Sample output:
aabca

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
S = str(input())


def get_kouho(SS):
    Scon = SS + SS[::-1]
    topchar = sorted(list(Scon))[0]
    smallScon = [Scon[i:i + N] for i in range(N) if Scon[i]==topchar]
    smallScon.sort()
    smallScon_rev = [s[::-1] for s in smallScon if Scon[i+N]==topchar]
    smallScon_rev.sort()
    # print(smallScon)
    # print(smallScon_rev)
    kouho1 = smallScon[0]
    kouho2 = smallScon_rev[0]
    return kouho1, kouho2[::-1]  # kouho2はrevしてるので元に戻す


kouho1, kouho2 = get_kouho(S)
# print('kouhos',kouho1, kouho2)

for i in range(K - 1):
    kouho11, kouho12 = get_kouho(kouho1)
    kouho21, kouho22 = get_kouho(kouho2)
    kouhos = kouho11, kouho12, kouho21, kouho22
    print('kouhos', kouhos)
    kouho1 = sorted(kouhos)[0]
    kouho2 = sorted([s[::-1] for s in kouhos])[0][::-1]

print(sorted([kouho1, kouho2])[0])

Submission status: Runtime Error

Solution code:
def E(S, N):
    T = S[::-1]
    U = S+T
    return [U[i:N+i] for i in range(N)]

N, K = input().split()
N, K = int(N), int(K)
S = [input()]

for i in range(K):
    memory = []
    for s in S:
        memory += E(s, N)
    S = sorted(memory)[:N//2]
print(S[0])

Submission status: Runtime Error

Solution code:
def E(S, N):
    T = S[::-1]
    U = S+T
    return [U[i:N+i] for i in range(N)]

N, K = input().split()
N, K = int(N), int(K)
S = [input()]

for i in range(K):
    memory = []
    for s in S:
        memory += E(s, N)
    S = sorted(memory)[:N]
print(sorted(S)[0])

Submission status: Runtime Error

Solution code:
def E(S, N):
    T = S[::-1]
    U = S+T
    return [U[i:N+i] for i in range(N)]

N, K = input().split()
N, K = int(N), int(K)
S = [input()]

for i in range(K):
    S = sorted(S)[:N//3]
    memory = []
    for s in S:
        memory.append(E(s, N))
    S = [s for i in range(len(memory)) for s in memory[i]]
print(sorted(S)[0])

Submission status: Runtime Error

Solution code:
n, k = [int(x) for x in input().split()]
s = input()

candidates = [s]
visited = set()
ret = ""


def get_smaller(target, current):
    if current == "":
        return target
    else:
        current_hex = current.encode('utf-8', 'replace').hex()
        current_hex = int(current_hex, 16)
        target_hex = target.encode('utf-8', 'replace').hex()
        target_hex = int(target_hex, 16)
        if target_hex < current_hex:
            return target
        else:
            return current


minimum_char = 'z'
for item in s:
    minimum_char = get_smaller(item, minimum_char)

flg = False
for _ in range(k):
    tmp_candidates = []
    for _ in range(len(candidates)):
        cand = candidates.pop(0)
        ret = get_smaller(cand, ret)
        candr = cand[::-1]
        new_s = cand + candr

        cnt = 0
        for i in range(1, len(new_s) - n + 1):
            new_cand = new_s[i:i+n]
            if new_cand in visited:
                cnt += 1
            else:
                visited.add(new_cand)
                tmp_candidates.append(new_cand)
                ret = get_smaller(new_cand, ret)
        if cnt == len(new_s) - n or ret == minimum_char * n:
            flg = True
        if flg:
            break
    if flg:
        break
    else:
        candidates.extend(tmp_candidates)

print(ret)

Submission status: Runtime Error

Solution code:
def E(S, N):
    T = S[::-1]
    U = S+T
    return [U[i:N+i] for i in range(N)]

N, K = input().split()
N, K = int(N), int(K)
S = [input()]
for i in range(K):
    memory = []
    for s in S:
        memory.append(E(s, N))
    S = [s for i in range(len(memory)) for s in memory[i]]
print(sorted(S)[0])

Submission status: Runtime Error

Solution code:
U = ""
lines = input().split(" ")
N = int(lines[0])
K = int(lines[1])
S = input()
 
if N == 1 && K == 1:
  print(S)
else:
  T = S[::-1]
  
  for i in range(K):
    U += S
    U += T
 
  num = len(U) 
  arr = [U[j : (j+ N)] for j in range(num) if j + N <= num]        
  arr.sort()
 
  print(arr[0])

Submission status: Runtime Error

Solution code:
U = ""
arr = []
lines = input().split(" ")
N = int(lines[0])
K = int(lines[1])
S = input()

if N == 1 && K == 1:
  print(S)
else:
  T = S[::-1]
  
  for i in range(K):
    U += S
    U += T

  num = len(U) 
  arr = [U[j : (j+ N)] for j in range(num) if j + N <= num]        
  arr.sort()
 
  print(arr[0])