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: Runtime Error

Solution code:
import sys
import math
import itertools
from heapq import heapify, heappop, heappush
from sys import stdin, stdout, setrecursionlimit
from bisect import bisect, bisect_left, bisect_right
from collections import defaultdict, deque


# d = defaultdict(lambda: 0)
# setrecursionlimit(10**7)
# inf = float("inf")


##### stdin ####
def LM(t, r): return list(map(t, r))
def R(): return stdin.readline()
def RS(): return R().split()
def I(): return int(R())
def F(): return float(R())
def LI(): return LM(int,RS())
def LF(): return LM(float,RS())
def ONE_SL(): return list(input())
def ONE_IL(): return LM(int, ONE_SL())
def ALL_IL(): return LM(int,stdin)

##### tools #####
def ap(f): return f.append
def pll(li): print('\n'.join(LM(str,li)))
def pljoin(li, s): print(s.join(li))


##### Library ####


##### main #####
def main():

    input_S = input()
    K = I() - 1

    # input_S = 'abcaa'
    # K = 2

    len_S = len(input_S)
    unique_S = len(set(input_S))
    
    lis = set()
    min_s = 'z'

    if len_S == 1:
        print(input_S)

    else:
        for i in range(len_S):
            for j in range(len_S):
                if input_S[j] > min_s:
                    continue

                s = input_S[j:j+i+1]
                lis.add(s)

            if len(lis) < K:
                k = unique_S-1
            else:
                k = K
            tmp = sorted(lis)[k]
            if min_s == tmp:
                print(tmp)
                sys.exit()
            min_s = tmp
        print(sorted(lis)[K])

   
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
import math
import itertools
from heapq import heapify, heappop, heappush
from sys import stdin, stdout, setrecursionlimit
from bisect import bisect, bisect_left, bisect_right
from collections import defaultdict, deque


# d = defaultdict(lambda: 0)
# setrecursionlimit(10**7)
# inf = float("inf")


##### stdin ####
def LM(t, r): return list(map(t, r))
def R(): return stdin.readline()
def RS(): return R().split()
def I(): return int(R())
def F(): return float(R())
def LI(): return LM(int,RS())
def LF(): return LM(float,RS())
def ONE_SL(): return list(input())
def ONE_IL(): return LM(int, ONE_SL())
def ALL_IL(): return LM(int,stdin)

##### tools #####
def ap(f): return f.append
def pll(li): print('\n'.join(LM(str,li)))
def pljoin(li, s): print(s.join(li))


##### Library ####


##### main #####
def main():

    input_S = input()
    K = I() - 1

    # input_S = 'abcaa'
    # K = 2

    len_S = len(input_S)
    unique_S = len(set(input_S))
    
    lis = set()
    min_s = 'z'

    if len_S == 1:
        print(input_S)

    else:
        for i in range(len_S):
            for j in range(len_S):
                if input_S[j] > min_s:
                    continue

                s = input_S[j:j+i+1]
                lis.add(s)

            if len(lis) < K:
                k = unique_S-1
            else:
                k = K
            tmp = sorted(lis)[k]
            if min_s == tmp:
                sys.exit()
            min_s = tmp
        print(sorted(lis)[K])

   
if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

def count(head):
    cnt = 0
    for i in range(len(s)):
        if i+len(head)-1<len(s) and s[i:i+len(head)]==head:
            cnt += len(s)-i
    return cnt

def solve50(head, K):
    #print('**', head, K)
    W = []
    for i in range(len(s)):
        if i+len(head)-1<len(s) and s[i:i+len(head)]==head:
            for j in range(i, len(s)):
                W.append(s[i:j+1])
                #print(' ', s[i:j+1])
    W = list(set(W))
    W.sort()
    #print(W)
    if len(W)>=K:
        return W[K-1], 0
    else:
        K -= len(W)
        return 0, K

def solve(head, K):
    #print('*', head, K)
    if count(head)<=50:
        return solve50(head, K)
    for a in alphabet:
        if head + a in s:
            #return solve(head + a, K)
            return head + a, K


alphabet = 'abcdefghijklmnopqrstuvwxyz'

for a in alphabet:
    if not a in s:
        continue

    head = a
    while True:
        ans, K = solve(head, K)
        #print(ans, K)
        if K==0:
            print(ans)
            exit()
        else:
            head = ans

#print('*')

Submission status: Runtime Error

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

def count(head):
    cnt = 0
    for i in range(len(s)):
        if i+len(head)-1<len(s) and s[i:i+len(head)]==head:
            cnt += len(s)-i
    return cnt

def solve50(head, K):
    #print('**', head, K)
    W = []
    for i in range(len(s)):
        if i+len(head)-1<len(s) and s[i:i+len(head)]==head:
            for j in range(i, len(s)):
                W.append(s[i:j+1])
                #print(' ', s[i:j+1])
    W = list(set(W))
    W.sort()
    #print(W)
    if len(W)>=K:
        return W[K-1], 0
    else:
        K -= len(W)
        return 0, K

def solve(head, K):
    #print('*', head, K)
    if count(head)<=50:
        return solve50(head, K)
    for a in alphabet:
        if head + a in s:
            #return solve(head + a, K)
            return head + 1, K


alphabet = 'abcdefghijklmnopqrstuvwxyz'

for a in alphabet:
    if not a in s:
        continue

    head = a
    while True:
        ans, K = solve(head, K)
        #print(ans, K)
        if K==0:
            print(ans)
            exit()
        else:
            head = ans

#print('*')

Submission status: Runtime Error

Solution code:
string = input()
k = int(input())
if len(string) > k:
    substrs = set()
    ls = sorted(list(string))
    for i in range(3):
        for s, c in enumerate(string):
            if c == ls[i]:
                for l in range(1, k+1):
                    substrs.add(string[s:s+l])
    substrs = list(substrs)
    substrs.sort()
    print(substrs[k-1])

else:
    substrs = set()
    for leng in range(1, len(string) + 1):
        for s in range(0, len(string) - leng + 1):
            substrs.add(string[s:s+leng])
    substrs = list(substrs)
    substrs.sort()
    print(substrs[k-1])

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
def inpl(): return map(int, input().split())
N = int(input())
balls = [input().replace(" ", "") for _ in range(2*N)] + ["END"]

B = ["END"] + ["B{}".format(i) for i in range(1, N+1)[::-1]]
W = ["END"] + ["W{}".format(i) for i in range(1, N+1)[::-1]]

ans = 0
for i in range(2*N):
    b = balls.index(B[-1])
    w = balls.index(W[-1])
    if b < w:
        if b != i:
            ans += b-i
            del balls[b]
            balls.insert(i, B[-1])
        B.pop()
    else:
        if w != i:
            ans += w-i
            del balls[w]
            balls.insert(i, W[-1])
        W.pop()

print(ans)

Submission status: Runtime Error

Solution code:
import math
import itertools
from heapq import heapify, heappop, heappush
from sys import stdin, stdout, setrecursionlimit
from bisect import bisect, bisect_left, bisect_right
from collections import defaultdict, deque


# d = defaultdict(lambda: 0)
# setrecursionlimit(10**7)
# inf = float("inf")


##### stdin ####
def LM(t, r): return list(map(t, r))
def R(): return stdin.readline()
def RS(): return R().split()
def I(): return int(R())
def F(): return float(R())
def LI(): return LM(int,RS())
def LF(): return LM(float,RS())
def ONE_SL(): return list(input())
def ONE_IL(): return LM(int, ONE_SL())
def ALL_IL(): return LM(int,stdin)

##### tools #####
def ap(f): return f.append
def pll(li): print('\n'.join(LM(str,li)))
def pljoin(li, s): print(s.join(li))


##### Library ####



##### main #####
def main():
    input_S = input()
    K = I() - 1

    # input_S = "abcde" * 1000
    # K = 4
        
    len_S = len(input_S)
    lis = set()
    min_s = 'z'
    if len_S == 1:
        print(input_S)

    else:
        for i in range(len_S):
            for j in range(len_S):

                if input_S[j] > min_s:
                    continue
                    
                s = input_S[j:j+i+1]
                lis.add(s)

            min_s = sorted(lis)[K]

        print(sorted(set(lis))[K])

if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

def count(head):
    cnt = 0
    for i in range(len(s)):
        if i+len(head)-1<len(s) and s[i:i+len(head)]==head:
            cnt += len(s)-i
    return cnt

def solve50(head, K):
    #print('**', head, K)
    W = []
    for i in range(len(s)):
        if i+len(head)-1<len(s) and s[i:i+len(head)]==head:
            for j in range(i, len(s)):
                W.append(s[i:j+1])
                #print(' ', s[i:j+1])
    W = list(set(W))
    W.sort()
    #print(W)
    if len(W)>=K:
        return W[K-1], 0
    else:
        K -= len(W)
        return 0, K

def solve(head, K):
    #print('*', head, K)
    if count(head)<=50:
        return solve50(head, K)
    for a in alphabet:
        if head + a in s:
            return solve(head + a, K)


alphabet = 'abcdefghijklmnopqrstuvwxyz'

for a in alphabet:
    if not a in s:
        continue

    ans, K = solve(a, K)
    #print(ans, K)
    if K==0:
        print(ans)
        exit()

#print('*')

Submission status: Runtime Error

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

x = ['a', 'b', 'ab', 'ba', 'aba']
a=[]
m = min(s)
for i in range(len(s)):
    a.append(s[i])
    if s[i]==m:
        a.append(s[i:min(len(s)-1,i+2)])
        a.append(s[i:min(len(s)-1,i+3)])
        a.append(s[i:min(len(s)-1,i+4)])
        a.append(s[i:min(len(s)-1,i+5)])
a=list(set(a))
a.sort()
if a[0]=='':
    a=a[1:]
print(a[k-1])

Submission status: Runtime Error

Solution code:
string = input()
k = int(input())
if len(string) >= k:
    substrs = set()
    ls = sorted(list(string))
    for i in range(k):
        for s, c in enumerate(string):
            if c == ls[i]:
                for l in range(1, k+1):
                    substrs.add(string[s:s+l])
    substrs = list(substrs)
    substrs.sort()
    print(substrs[k-1])

else:
    substrs = set()
    for leng in range(1, len(string)):
        for s in range(0, len(string) - leng):
            substrs.add(string[s:s+leng])
    substrs = list(substrs)
    substrs.sort()
    print(substrs[k-1])

Submission status: Runtime Error

Solution code:
string = input()
k = int(input())
if len(string) >= k:
    substrs = set()
    ls = sorted(list(string))
    for i in range(5):
        for s, c in enumerate(string):
            if c == ls[i]:
                for l in range(1, 5+1):
                    substrs.add(string[s:s+l])
    substrs = list(substrs)
    substrs.sort()
    print(substrs[k-1])

else:
    substrs = set()
    for leng in range(1, len(string)):
        for s in range(0, len(string) - leng):
            substrs.add(string[s:s+leng])
    substrs = list(substrs)
    substrs.sort()
    print(substrs[k-1])

Submission status: Runtime Error

Solution code:
import math
import itertools
from heapq import heapify, heappop, heappush
from sys import stdin, stdout, setrecursionlimit
from bisect import bisect, bisect_left, bisect_right
from collections import defaultdict, deque


# d = defaultdict(lambda: 0)
# setrecursionlimit(10**7)
# inf = float("inf")


##### stdin ####
def LM(t, r): return list(map(t, r))
def R(): return stdin.readline()
def RS(): return R().split()
def I(): return int(R())
def F(): return float(R())
def LI(): return LM(int,RS())
def LF(): return LM(float,RS())
def ONE_SL(): return list(input())
def ONE_IL(): return LM(int, ONE_SL())
def ALL_IL(): return LM(int,stdin)

##### tools #####
def ap(f): return f.append
def pll(li): print('\n'.join(LM(str,li)))
def pljoin(li, s): print(s.join(li))


##### Library ####



##### main #####
def main():
    input_S = input()
    K = I() - 1

    len_S = len(input_S)
    lis = set()

    if len_S == 1:
        print(input_S)
    else:
        for i in range(len_S - 1):
            for j in range(len_S - i-1):
                s = input_S[j:j+i+1]
                lis.add(s)

        print(sorted(lis)[K])

if __name__ == '__main__':
	main()

Submission status: Runtime Error

Solution code:
s = str(input())
k = str(input())
lis = []
for u in range(6):
	for i in range(len(s)):
		try:
			if s[i:i+u] == "":
				continue
			if s[i:i+u] not in lis:
				lis.append(s[i:i+u])
		except:
			continue
lis.sort()
print(lis[k-1])

Submission status: Runtime Error

Solution code:
s = str(input())
k = str(input())
lis = []
ans = "zzz"
li = ["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"]
for k in range(6):
	for i in range(len(s)):
		try:
			if s[i:i+k] == "":
				continue
			if s[i:i+k] not in lis:
				lis.append(s[i:i+k])
		except:
			continue
lis.sort()

for i in range(k-1):
	lis.remove(lis[0])

print(lis[0])

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;
#define mp       make_pair
#define pb       push_back
#define all(x)   (x).begin(),(x).end()
#define YES() printf("YES\n")
#define NO() printf("NO\n")
#define Yes() printf("Yes\n")
#define No() printf("No\n")
#define in(x,y,h,w) x >= 0 && x < h && y >= 0 && y < w

#define int long long
//typedef    long long          ll;
typedef    vector<bool>       vb;
typedef    vector<int>        vi;
typedef    vector<vb>         vvb;
typedef    vector<vi>         vvi;
typedef    pair<int,int>      P;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
 
const int INF=1e+18;
const double EPS=1e-9;
const int MOD=1000000007;
 
const int dx[]={1,0,-1,0},dy[]={0,-1,0,1};

signed main(){
	string s,a[5];
	int n,k;
	cin >> s >> k;
	n = s.length();
	for(int i = 0;i < 5;i++) a[i] = "zzzzzzzzzz";
	for(int i = 0;i < n;i++){
		for(int j = 1;j <= 5 && i + j <= n;j++){
			string t = s.substr(i,j);
			for(int l = 0;l < 5;l++){
				if(t == a[l]) break;
				else if(t < a[l]) swap(t,a[l]);
			}
		}
	}
	cout << a[k - 1] << endl;
	return 0;
}