Problem:


Score : 300 points

Problem Statement

You are given a string s.
Among the different substrings of s, print the K-th lexicographically smallest one.

A substring of s is a string obtained by taking out a non-empty contiguous part in s.
For example, if s = ababc, a, bab and ababc are substrings of s, while ac, z and an empty string are not.
Also, we say that substrings are different when they are different as strings.

Let X = x_{1}x_{2}...x_{n} and Y = y_{1}y_{2}...y_{m} be two distinct strings. X is lexicographically larger than Y if and only if Y is a prefix of X or x_{j} > y_{j} where j is the smallest integer such that x_{j} \neq y_{j}.

Constraints

1 ≤ |s| ≤ 5000

s consists of lowercase English letters.

1 ≤ K ≤ 5

s has at least K different substrings.

Partial Score

200 points will be awarded as a partial score for passing the test set satisfying |s| ≤ 50.

Input

Input is given from Standard Input in the following format:

s
K

Output

Print the K-th lexicographically smallest substring of K.

Sample Input 1

aba
4

Sample Output 1

b

s has five substrings: a, b, ab, ba and aba.
Among them, we should print the fourth smallest one, b.
Note that we do not count a twice.

Sample Input 2

atcoderandatcodeer
5

Sample Output 2

andat

Sample Input 3

z
1

Sample Output 3

z



Sample input:
aba
4


Sample output:
b

Submission status: Wrong Answer

Solution code:
import sys
import os
import math
import bisect
import itertools
import collections
import heapq
import queue
import array

# 時々使う
# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
# from decimal import Decimal
# from collections import defaultdict, deque

# 再帰の制限設定
sys.setrecursionlimit(10000000)


def ii(): return int(sys.stdin.buffer.readline().rstrip())
def il(): return list(map(int, sys.stdin.buffer.readline().split()))
def fl(): return list(map(float, sys.stdin.buffer.readline().split()))
def iln(n): return [int(sys.stdin.buffer.readline().rstrip())
                    for _ in range(n)]


def iss(): return sys.stdin.buffer.readline().decode().rstrip()
def sl(): return list(map(str, sys.stdin.buffer.readline().decode().split()))
def isn(n): return [sys.stdin.buffer.readline().decode().rstrip()
                    for _ in range(n)]


def lcm(x, y): return (x * y) // math.gcd(x, y)


MOD = 10 ** 9 + 7
INF = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    S = iss()
    K = ii()

    substring = set()
    for i in range(1, len(S)+1):
        for j in range(i):
            if j == i:
                break
            substring.add(S[j:i])
        if len(substring) >= K:
            break
    ret = sorted(list(substring))
    print(ret[K-1])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
s = input().rstrip()
N = len(s)
K = int(input())

c = []
for i in range(N):
    for j in range(i+1, N+1):
        if len(c) < K:
            c.append(s[i:j])
        else:
            if s[i:j] in c:
                continue

            if c[K-1] < s[i:j]:
                break
            else:
                c[K-1] = s[i:j]
                c.sort()

print(c[-1])

Submission status: Wrong Answer

Solution code:
s = input()
k = int(input())
substring = set([])
for i in range(len(s)):
    for j in range(0, len(s)-i):
        substring.add(s[j:i+j+1])
ans = list(substring)
ans.sort()
ans.sort(key=lambda s:len(s))
print(ans[-k])

Submission status: Wrong Answer

Solution code:
s = input()
k = int(input())
a = []

for i in range(k+1):
    for j in range(i+1, k+2):
        a.append(s[i:j])

res = sorted(set(a))
print(res[k-1])

Submission status: Wrong Answer

Solution code:
s = input()
k = int(input())
a = []

for i in range(k):
    for j in range(i+1, k+1):
        a.append(s[i:j])

res = sorted(set(a))
print(res[k-1])

Submission status: Wrong Answer

Solution code:
S = input().rstrip()
N = len(S)
K = int(input())
A = set()
for i in range(N):
    A.add(S[i:])
A = list(A)
A.sort()
cnt, i = 0, 0
while i < len(A) and cnt + len(A[i]) < K:
    cnt += len(A[i])
    i += 1
print(A[i][:K-cnt])

Submission status: Wrong Answer

Solution code:
def main2():
    S=list(input())
    K=int(input())
    N=len(S)

    P=sorted(S)
    l=[]
    k=0
    while len(l)<=5 and k<N:
        for n in range(N):
            if S[n]==P[k]:
                for i in range(1,6):
                    if n+i<=N:
                        l.append("".join(S[n:n+i]))
        k+=1
    l.sort()
    cnt=1
    if len(l)==1:
        print(l[0])
    else:
        for n in range(1,len(l)):
            if l[n]!=l[n-1]:
                cnt+=1
            if cnt==K:
                print(l[n])
                break

if __name__=="__main__":
    main2()

Submission status: Wrong Answer

Solution code:
s = input()
n = len(s)
k = int(input())
atoz = "abcdefghijklmnopqrstuvwxyz"
substring = []
for i in range(26):
    idx = s.find(atoz[i])
    while idx != -1:
        if idx + 5 > n-1:
            substring.append(s[idx:])
        else:
            substring.append(s[idx:idx+5])
        idx = s.find(atoz[i], idx+5)
substring.sort()
#print(substring)
for sub in substring:
    m = len(sub)
    if m >= k:
        print(sub[:k])
        exit()
    else:
        k -= m

Submission status: Wrong Answer

Solution code:
L=list()
s=input()
K=int(input())
for i in range(len(s)):
  for j in range(i+1,len(s)+1):
    L.append(str(s[i:j]))
  if len(L)>K:
    L=list(sorted(set(L))[:K])
print(L[-1])

Submission status: Wrong Answer

Solution code:
import sys
s = input()
K = int(input())

a_list = sorted(set(s))
for i in a_list:
  if K == 1:
    print(i)
    sys.exit()
  p = []
  for j, x in enumerate(s):
    if x == i:
      p.append(s[j:min(j+K,len(s))])
  p.sort()
  print(p)
  t = K
  for j in range(len(p)):
    if j != len(p) - 1:
      if p[j] == p[j+1][0:len(p[j])]:
        continue
    if len(p[j]) < t:
      t -= len(p[j]) - 1
    else:
      print(p[j][0:t])
      sys.exit()
  K = t - 1

Submission status: Wrong Answer

Solution code:
import sys
s = input()
K = int(input())

a_list = sorted(set(s))
for i in a_list:
  if K == 1:
    print(i)
    sys.exit()
  p = []
  q = -1
  for j, x in enumerate(s):
    if x == i and q < j:
      p.append(s[j:min(j+K,len(s))])
      q = j + K
  p.sort()
  t = K
  for j in p:
    if len(j) < t:
      t -= len(j) - 1
    else:
      print(j[0:t])
      sys.exit()
  K = t - 1

Submission status: Wrong Answer

Solution code:
import sys
s = input()
K = int(input())

a_list = sorted(set(s))
for i in a_list:
  if K == 1:
    print(i)
    sys.exit()
  p = []
  q = 0
  for j, x in enumerate(s):
    if x == i and q < j:
      p.append(s[j:min(j+K,len(s))])
      q = j + K
  p.sort()
  t = K
  for j in p:
    if len(j) < t:
      t -= len(j) - 1
    else:
      print(j[0:t])
      sys.exit()
  K = t - 1

Submission status: Wrong Answer

Solution code:
import sys
s = input()
K = int(input())

a_list = sorted(set(s))
for i in a_list:
  if K == 1:
    print(i)
    sys.exit()
  p = []
  for j, x in enumerate(s):
    if x == i:
      p.append(s[j:min(j+K,len(s))])
  p.sort()
  t = K
  for j in p:
    if len(j) < t:
      t -= len(j) - 1
    else:
      print(j[0:t])
      sys.exit()
  K = t - 1

Submission status: Wrong Answer

Solution code:
import sys
s = input()
K = int(input())

a_list = sorted(set(s))
for i in a_list:
  if K == 1:
    print(i)
    sys.exit()
  p = []
  for j, x in enumerate(s):
    if x == i:
      p.append(s[j:min(j+K,len(s))])
  p.sort()
  print(p)
  t = K
  for j in p:
    if len(j) < K:
      t -= len(j) - 1
    else:
      print(j[0:t])
      sys.exit()
  K = t

Submission status: Wrong Answer

Solution code:
s = str(input())
K = int(input())
# sがabcac の場合、a,bca,ac などは部分列(substring
# abc とabの場合、abの方が辞書順で小さいと判断する。
# abc とabaの場合、abaの方が小さい

substrings = set([])
for i in range(len(s) + 1):
    for j in range(i + 1, len(s) + 1):
        # print(i, j)
        substrings.add(s[i:j])

# print(substrings)
substrings = sorted(sorted(substrings), key=len)
# print(substrings)
print(substrings[K - 1])

Submission status: Wrong Answer

Solution code:
from collections import Counter
def main():
    s=input()
    k=int(input())
    p=sorted(Counter(s).items(), key=lambda x: x[1], reverse=True)
    count = 1
    for i in range(len(p)):
        for t in g(p[i][0], s):
            if count == k:
                print(t)
                return
            count += 1
        
def g(s, ss):
    sumi = set()
    lens = len(ss)
    for l in range(lens):
        for i in range(lens):
            if i+l >= lens:
                break
            res = ss[i:i+l+1]
            if (ss[i] == s) and (res not in sumi):
                sumi.add(res)
    return sorted(sumi)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())
S = input()
K = int(input())

x = set(list(S))

for w in range(2, len(S) + 1):
    for i in range(len(S)):
        if i + w > len(S):
            continue
        x.add(S[i:i+w])
    if len(x) >= K:
        break


x = sorted(list(x))
print(x[K - 1])

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
from collections import defaultdict
def main():
    s = list(input())
    k = int(input())
    k -= 1

    d1 = defaultdict(list)
    for i, c in enumerate(s):
        d1[c].append(i)
    d2 = sorted(d1.items())

    lens = len(s)
    for d2e in d2:
        subnum = 1
        for d2ee in d2e[1]:
            subnum += (lens - d2ee - 1)
        if subnum > k:
            subs = set()
            subs.add(d2e[0])
            for d2ee in d2e[1]:
                for i1 in range(d2ee + 1, lens + 1):
                    subs.add("".join(s[d2ee:i1]))
            subsl = list(subs)
            subsl.sort()
            print(subsl[k])
            sys.exit()
        else:
            k -= subnum


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
s = input()
K = int(input())

S = set([])
for i in range(len(s)):
    for j in range(i + 1, i + 1 + K):
        print(f'{s[i:j]=}')
        S.add(s[i:j])
# print(f'{S=}')
# print(f'{sorted(S)=}')
ans = sorted(S)[K - 1]
print(ans)

Submission status: Wrong Answer

Solution code:
s = input()
K = int(input())

S = set([])
for i in range(len(s)):
    for j in range(i + 1, i + 1 + K):
        print(f'{s[i:j]=}')
        S.add(s[i:j])
print(f'{S=}')
print(f'{sorted(S)=}')
ans = sorted(S)[K - 1]
print(ans)

Submission status: Wrong Answer

Solution code:
def kThLexString(st, k, n): 
    # Set to store the unique substring 
    z = set()  
  
    for i in range(n): 
        # String to create each substring 
        pp = ""  
  
        for j in range(i, i + k): 
  
            if (j >= n): 
  
                break
  
            pp += s[j] 
            # adding to set 
            z.add(pp)  
  
    # converting set into a list 
    fin = list(z)  
      
    # sorting the strings int the list 
    # into lexicographical order 
    fin.sort()  
  
    # printing kth substring 
    print(fin[k - 1])  
  
  
s = "geeksforgeeks"
  
k = 5
  
n = len(s) 
kThLexString(s, k, n)

Submission status: Wrong Answer

Solution code:
from operator import itemgetter
s = [[string, i] for i, string in enumerate(input())]
k = int(input())

cand = sorted(s, key = itemgetter(0))[:k] if len(s) >= k else sorted(s, key = itemgetter(0))
ans_cand = []
def check(list, k):
    string, ind = list
    temp_s = ''
    for i in range(k): 
        if ind + i > len(s) - 1:break
        temp_s += s[ind + i][0]
        ans_cand.append(temp_s)

for t in cand:
    check(t, k)
    
ans_cand.sort()
pre = ans_cand.pop(0)
k -= 1
while k != 0:
    temp = ans_cand.pop(0)
    if pre == temp:continue
    pre = temp
    k -= 1
print(pre)

Submission status: Wrong Answer

Solution code:
from operator import itemgetter
s = [[string, i] for i, string in enumerate(input())]
k = int(input())

cand = sorted(s, key = itemgetter(0))[:k]
ans_cand = []
def check(list, k):
    string, ind = list
    temp_s = ''
    for i in range(k): 
        if ind + i > len(s) - 1:break
        temp_s += s[ind + i][0]
        ans_cand.append(temp_s)

for t in cand:
    check(t, k)
    
ans_cand.sort()
pre = ans_cand.pop(0)
k -= 1
while k != 0:
    temp = ans_cand.pop(0)
    if pre == temp:continue
    pre = temp
    k -= 1
print(pre)

Submission status: Wrong Answer

Solution code:
from itertools import combinations

# input
s = input()
K = int(input())

# check
case = []
append = case.append
for i in range(1, len(s) + 1):
    for c in combinations(list(s), i):
        if "".join(c) in s and "".join(c) not in case:
            append("".join(c))

print(case[-K])

Submission status: Wrong Answer

Solution code:
import re

s = input()
n = len(s)
k = int(input())
l = []
for i in range(26):
  m_list = [m.start() for m in re.finditer(chr(ord('a')+i), s)]
  #print(m_list)
  

  c = 1
  while len(m_list) > 0 and len(l) < k:
    for start in m_list:
      if start + c <= n:
        if not s[start:start+c] in l:
          l.append(s[start:start+c])
      else:
        m_list.pop()
    c += 1
  if len(l) >= k:
    break
#print(l)
print(sorted(l)[k-1])

Submission status: Wrong Answer

Solution code:
import re

s = input()
n = len(s)
k = int(input())
l = []
for i in range(26):
  m_list = [m.start() for m in re.finditer(chr(ord('a')+i), s)]
  # print([m.span() for m in re.finditer(chr(ord('a')+i), s)])
  # [(2, 4), (6, 8)]
  c = 2
  while len(m_list) > 0 and len(l) < k:
    l.append(chr(ord('a')+i))
    for start in m_list:
      if start + c <= n:
        l.append(s[start:start+c])
      else:
        continue
    c += 1
  if len(l) >= k:
    break
print(sorted(l)[k-1])

Submission status: Wrong Answer

Solution code:
s = input()
k = int(input())

subs_list = []
for i in range(len(s)):
    for j in range(i+1, k+1):
        subs_list.append(s[i:j])

ans = sorted(set(subs_list))
print(ans[k-1])

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from itertools import combinations_with_replacement 
from heapq import heapify, heappop, heappush
def main():
    s = readline().rstrip().decode()
    K = int(readline())
    N = len(s)
    p = [int(i) for i in range(N)]
    hp = []
    heapify(hp)
    #K番目のsubsitringは長さがK以下のsubstrigの集合に必ず含まれる
    #K<=5であるから列挙される要素数は最大でも26^5(およそ10,000,000)
    for l, r in combinations_with_replacement(p, 2):
        sub = s[l:r+1]
        ln = len(sub)
        if ln <= K:  
            heappush(hp, sub)
    S = set()
    while len(hp)>0:
        v = heappop(hp)
        S.add(v)
        if len(S) == K:
            print(v)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
s = input()
k = int(input())
n = len(s)

m = {}
ky = ''
pre = ''
for i in range(n):
    now = s[i]
    if pre != now:
        if ky != '':
            if ky in m.keys():
                m[ky] += [i-1]
            else:
                m[ky] = [i-1]
        ky = now
    else: ky += now
    pre = now

if ky != '':
    if ky in m.keys(): m[ky] += [i]
    else: m[ky] = [i]

# print(s,k,n)
m = list(m.items())
m.sort()
# print(*m,sep='\n')

for ky,ixs in m:
    c = set()
    for i in ixs:
        for j in range(len(s[i:])):
            # c.add(s[i:i+j+1])
            c.add(ky+s[i+len(ky):i+j+1])
            # print(ky+s[i+1:i+j+1])

    c = list(c)
    c.sort()
    # print('c',c)
    for ans in c:
        k-= len(ky)
        if k == 0:
            print(ans)
            exit()
        elif k < 0:
            # print('k',k)
            k += len(ky)
            # print('k',k)
            print(ans[:k])
            exit()
print(s)

Submission status: Wrong Answer

Solution code:
s = input()
k = int(input())
n = len(s)

m = {}
ky = ''
pre = ''
for i in range(n):
    now = s[i]
    if pre != now:
        if ky != '':
            if ky in m.keys():
                m[ky] += [i-1]
            else:
                m[ky] = [i-1]
        ky = now
    else: ky += now
    pre = now

if ky != '':
    if ky in m.keys(): m[ky] += [i]
    else: m[ky] = [i]

# print(s,k,n)
m = list(m.items())
m.sort()
# print(*m,sep='\n')

for ky,ixs in m:
    c = set()
    for i in ixs:
        for j in range(len(s[i:])):
            # c.add(s[i:i+j+1])
            c.add(ky+s[i+1:i+j+1])
            # print(ky+s[i+1:i+j+1])
    c = list(c)
    c.sort()
    # print('c',c)
    for ans in c:
        # k -= 1
        k-= len(ky)
        if k == 0:
            print(ans)
            exit()
        elif k < 0:
            # print('k',k)
            k += len(ky)
            # print('k',k)
            print(ans[:k])
            exit()
print(s)

Submission status: Wrong Answer

Solution code:
s = input()
k = int(input())
n = len(s)

m = {}
ky = ''
pre = ''
for i in range(n):
    now = s[i]
    if pre != now:
        if ky != '':
            if ky in m.keys():
                m[ky] += [i-1]
            else:
                m[ky] = [i-1]
        ky = now
    else: ky += now
    pre = now

if ky != '':
    if ky in m.keys(): m[ky] += [i]
    else: m[ky] = [i]

# print(s,k,n)
m = list(m.items())
m.sort()
# print(*m,sep='\n')

for ky,ixs in m:
    c = set()
    for i in ixs:
        for j in range(len(s[i:])):
            # c.add(s[i:i+j+1])
            c.add(ky+s[i+1:i+j+1])
            # print(ky+s[i+1:i+j+1])
    c = list(c)
    c.sort()
    # print('c',c)
    for ans in c:
        # k -= 1
        k-= len(ky)
        if k == 0:
            print(ans)
            exit()
        elif k < 0:
            # print('k',k)
            k += len(ky)
            # print('k',k)
            # print(ans[:k])
            exit()
print(s)

Submission status: Wrong Answer

Solution code:
s = input()
k = int(input())
n = len(s)

m = {}
st = 0
while st < n:
    ed = st
    for c in s[st:]:
        if s[st] != c: break
        ed += 1
    ky = s[st:ed]
    if ky in m.keys():
        m[ky] += [st]
    else:
        m[ky] = [st]
    st = ed

# print(m)
m = list(m.items())
# print(m)
m.sort()
# print(m)

for ky,ixs in m:
    c = set()
    for i in ixs:
        for j in range(len(s[i:])):
            c.add(s[i:i+j+1])
    c = list(c)
    c.sort()
    for ans in c:
        k -= 1
        if k == 0:
            print(ans)
            exit()
print(s)

Submission status: Wrong Answer

Solution code:
s = input()
k = int(input())
n = len(s)

# print(s,k,n)

ks = {}
m = {}
for i in range(n):
    if s[i] in m.keys():
        m[s[i]] += [i]
    else:
        m[s[i]] = [i]

# "spam".startswith("sp")

for ky,ixs in m.items():
    c = set()
    for i in ixs:
        for j in range(len(s[i:])):
            c.add(s[i:i+j+1])
            # print(s[i:i+j+1])
    c = list(c)
    c.sort()
    # print(len(c),c)
    # print('---')
    for ans in c:
        k -= 1
        if k == 0:
            print(ans)
            exit()
print(s)

Submission status: Wrong Answer

Solution code:
s = input()
k = int(input())
n = len(s)

# print(s,k,n)

ks = {}
m = {}
for i in range(n):
    if s[i] in m.keys():
        m[s[i]] += [i]
    else:
        m[s[i]] = [i]

# "spam".startswith("sp")

for ky,ixs in m.items():
    c = set()
    for i in ixs:
        for j in range(len(s[i:])):
            c.add(s[i:i+j+1])
            # print(s[i:i+j+1])
    c = list(c)
    c.sort()
    # print(len(c),c)
    # print('---')
    k -= len(c)
    if k == 0:
        ans = c[-1]
        # print('ans',ans)
        print(ans)
        exit()
        pass
    elif k < 0:
        ans = c[k-1]
        # print('ans',ans)
        print(ans)
        exit()
        pass

print(s)

Submission status: Wrong Answer

Solution code:
s = input()
k = int(input())
n = len(s)

# print(s,k,n)

ks = {}
m = {}
for i in range(n):
    if s[i] in m.keys():
        m[s[i]] += [i]
    else:
        m[s[i]] = [i]

# "spam".startswith("sp")

for ky,ixs in m.items():
    c = set()
    for i in ixs:
        for j in range(len(s[i:])):
            c.add(s[i:i+j+1])
            # print(s[i:i+j+1])
    c = list(c)
    c.sort()
    # print(len(c),c)
    # print('---')
    k -= len(c)
    if k == 0:
        ans = c[-1]
        # print('ans',ans)
        print(ans)
        exit()
        pass
    elif k < 0:
        ans = c[k-1]
        # print('ans',ans)
        print(ans)
        exit()
        pass


print(m)

Submission status: Wrong Answer

Solution code:
S = input()
K = int(input())-1
result = [i for i in S]
result.append(S)
for i in range(len(S)):
  for j in range(i+1, len(S)):
    result.append(S[i:j])
result = list(set(result))
result.sort()
print(result[K])

Submission status: Wrong Answer

Solution code:
def main():
    S = input()
    N = len(S)
    K = int(input())
    top_k = []
    for i in range(N):
        for j in range(i + 1, N + 1):
            st = S[i:j]
            top_k.append(st)
            if len(top_k) > K:
                top_k = list(set(top_k))
                top_k.sort()
                top_k = top_k[:K]
    print(top_k[-1])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
S, k = open(0).read().split()
k = int(k)
x = set(S[:min(k, len(S))])
A = set()
for i, c in enumerate(S):
    if c in x:
        s = ''
        for j in range(i, min(i+k, len(S))):
            s += S[j]
            A.add(s)
print(sorted(A)[k-1])

Submission status: Wrong Answer

Solution code:
S = input()
K = int(input())

ans = set()

for i in range(len(S)):
    for j in range(len(S)+1):
        if (i+j)>=6:
            break
        if i==j:
            ans.add(S[i])
            continue
        if S[i:j]=="":
            continue
        ans.add(S[i:j])
ans = sorted(list(ans))
print(ans[K-1])

Submission status: Wrong Answer

Solution code:
import sys
import heapq
import re
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from fractions import gcd
from math import factorial, sqrt, ceil
from functools import lru_cache, reduce
INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)

# UnionFind
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

def is_prime(n):
    if n == 1:
        return False
    for i in range(2,int(n**0.5)+1):
        if n % i == 0:
            return False
    return True


# ワーシャルフロイド (任意の2頂点の対に対して最短経路を求める)
# 計算量n^3 (nは頂点の数)
def warshall_floyd(d, n):
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d


# ダイクストラ
def dijkstra_heap(s, edge, n):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

# 素因数分解
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

# 2数の最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

# リストの要素の最小公倍数
def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

# リストの要素の最大公約数
def gcd_list(numbers):
    return reduce(gcd, numbers)

# 素数判定



# limit以下の素数を列挙
def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P

# 同じものを含む順列
def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        # set（集合）型で重複を削除、ソート
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret


# ここから書き始める
s = input()
k = int(input())
n = len(s)
a = []
for i in range(n):
    for j in range(i + 1, n + 1):
        a.append(s[i : j])
a.sort()
cnt = 0
m = len(a)
for i in range(m):
    if i == 0:
        cnt += 1
    elif a[i] != a[i - 1]:
        cnt += 1
    if cnt == k:
        print(a[i])

Submission status: Wrong Answer

Solution code:
def main():
    s = input()
    k = int(input())
    d = len(s)
    m = set()
    if k >= d:
        for i in range(d + 1):
            for j in range(1, d - i + 1):
                m.add(s[i:i + j])
    else:
        for i in range(1, d - k + 1):
            for j in range(1, k + 1):
                m.add(s[i:i + j])

    m = list(m)
    m.sort()
    print(m[k - 1])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
s = input()
k = int(input())
n = len(s)

ansset= set()

for i in range(1,n+1):
    for j in range(n-i+1):
        ansset.add(s[j:j+i])

anslist = sorted(list(ansset))

print(anslist[k-1])

Submission status: Wrong Answer

Solution code:
s = input()
K = int(input())
d = list()
for l in range(len(s)):
  for r in range(l,len(s)): #左からl番目、右からr番目までの文字列
    n = s[l:r+1]
    d.append(n)
    d.sort()
    d = d[:6]
print(d[K-1])

Submission status: Wrong Answer

Solution code:
s = input()
k = int(input())
d = []
n = len(s)

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.readline

def main():
    S = readline().rstrip()
    K = int(readline())
    N = len(S)
    d = {a: set() for a in list('abcdefghijklmnopqrstuvwxyz')}
    for i in range(N):
        s = ''
        head = S[i]
        for j in range(i, N):
            s += S[j]
            d[head].add(s)

    for key, val in d.items():
        if K <= len(val):
            print(sorted(list(val))[K-1])
            return
        else:
            K -= len(val)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
import numpy as np
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    s=input()
    K=int(input())
    a=np.argsort(list(s))
    l=[]
    for i in a[:5]:
        for j in range(1,K+1):
            if i+j>len(s):
                continue
            l.append(s[i:i+j])
    l=list(set(l))
    l.sort()
    print(l[K-1])

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from bisect import *
s = str(input())
K = int(input())
ls = len(s)
l = []
for i in range(ls):
  for j in range(i+1,i+K+2):
    l.append(s[i:j])

l = list(set(l))
l = sorted(l)
print(l)

Submission status: Wrong Answer

Solution code:
from bisect import *
s = str(input())
K = int(input())
ls = len(s)
l = []
for i in range(ls):
  for j in range(i+1,i+K+2):
    l.append(s[i:j])
    print(s[i:j])
l = list(set(l))
l = sorted(l)
print(l)

Submission status: Wrong Answer

Solution code:
import string
import sys
letters=string.ascii_lowercase

s = input()
K = int(input())

cnt = 0
for i in range(26):
    ans = []
    for j in range(len(s)):
        if letters[i] == s[j]:
            ans.append(s[j:])
    ans.sort()
    for k in range(len(ans)):
        if k == 0:
            for l in range(len(ans[k])):
                cnt += 1
                if cnt == K:
                    print(ans[k][:l+1])
                    sys.exit()
        else:
            for l in range(1, len(ans[k])):
                cnt += 1
                if cnt == K:
                    print(ans[k][1:l+1])
                    sys.exit()

Submission status: Wrong Answer

Solution code:
import string
import sys
letters=string.ascii_lowercase

s = input()
K = int(input())

cnt = 0
for i in range(26):
    ans = []
    for j in range(len(s)):
        if letters[i] == s[j]:
            ans.append(s[j:])
    ans.sort()
    for k in range(len(ans)):
        if k == 0:
            for l in range(len(ans[k])):
                cnt += 1
                if cnt == K:
                    print(ans[k][0:l+1])
                    sys.exit()
        else:
            for l in range(1, len(ans[k])):
                cnt += 1
                if cnt == K:
                    print(ans[k][1:l+1])
                    sys.exit()

Submission status: Wrong Answer

Solution code:
import string
import sys
letters=string.ascii_lowercase

s = input()
K = int(input())

cnt = 0
for i in range(26):
    ans = []
    for j in range(len(s)):
        if letters[i] == s[j]:
            ans.append(s[j:])
    ans.sort()
    for k in range(len(ans)):
        if k == 0:
            cnt += len(ans[k])
            if cnt >= K:
                print(ans[k][0:-(cnt-K)])
                sys.exit()
        else:
            cnt += len(ans[k])-1
            if cnt >= K:
                print(ans[k][1:-(cnt-K)])
                sys.exit()

Submission status: Wrong Answer

Solution code:
#import collections
#aa = collections.Counter(a) # list to list
#from itertools import combinations # (string,3) 3回

mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def main():
    s = input()
    k = int(input())
    #LIST = {s}
    #for i in range(k):
    #    for j in range(len(s) - i):
    #        LIST.add(s[j:j+i+1])
    #print(LIST)
    #print(sorted(list(LIST))[k-1])
    # 辞書順で5番目、長さは最長でも5
    r = []
    for i in range(1,6): # 1 ~ 5 文字のながさ 1から5文字まで
        for j in range(len(s) - i + 1): # 見る範囲 len(s) - j  ~ len(s) - j + i まで最後まで見てる!
            r.append(s[j:j+i])
    print(r)
    print(sorted((set(r)))[k-1])


if __name__ == '__main__':
  main()