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: Time Limit Exceeded

Solution code:
def min5(numbers):
    list_n = list(numbers)
    min1 = "zzzzzz"
    min2 = "zzzzzzz"
    min3 = "zzzzzzzz"
    min4 = "zzzzzzzzz"
    min5 = "zzzzzzzzzz"
    for num in list_n:
        if num < min1:
            min1,min2,min3,min4,min5 = num,min1,min2,min3,min4
        elif min1 <= num < min2:
            min2,min3,min4,min5 = num,min2,min3,min4
        elif min2 <= num < min3:
            min3,min4,min5 = num, min3,min4
        elif min3 <= num < min4:
            min4,min5 = num,min4
        elif min4 <= num < min5:
            min5 = num
        else:
            pass
    return min1,min2,min3,min4,min5

list_alp = list("abcdefghijklmnopqrstuvwxyz")
s = str(input())
k = int(input())
len_s = len(s)
dict_s = {}
trigger = []
count = 0
for i in range(26):
    if list_alp[i] in s:
        trigger.append(list_alp[i])
        count += 1
    if count >= 3:
        break
for i in range(len_s):
    if not s[i] in trigger[0]:
        continue
    else:
        for j in range(i,min(i+5,len_s)):
            try:
                dict_s[ s[i:j+1] ] += 1
            except KeyError:
                dict_s[ s[i:j+1] ] = 1
if len(dict_s) < 5:
    try:
        for i in range(len_s):
            if not s[i] in trigger[1]:
                continue
            else:
                for j in range(i,max(i+5,len_s)):
                    try:
                        dict_s[ s[i:j+1] ] += 1
                    except KeyError:
                        dict_s[ s[i:j+1] ] = 1
    except IndexError:
        pass

if len(dict_s) < 5:
    try:
        for i in range(len_s):
            if not s[i] in trigger[2]:
                continue
            else:
                for j in range(i,max(i+5,len_s)):
                    try:
                        dict_s[ s[i:j+1] ] += 1
                    except KeyError:
                        dict_s[ s[i:j+1] ] = 1
    except IndexError:
        pass

list_ans = []
for key in dict_s.keys():
    list_ans.append(key)
print(min5(list_ans)[k-1])

Submission status: Time Limit Exceeded

Solution code:
def min5(numbers):
    list_n = list(numbers)
    min1 = "zzzzzz"
    min2 = "zzzzzzz"
    min3 = "zzzzzzzz"
    min4 = "zzzzzzzzz"
    min5 = "zzzzzzzzzz"
    for num in list_n:
        if num < min1:
            min1,min2,min3,min4,min5 = num,min1,min2,min3,min4
        elif min1 <= num < min2:
            min2,min3,min4,min5 = num,min2,min3,min4
        elif min2 <= num < min3:
            min3,min4,min5 = num, min3,min4
        elif min3 <= num < min4:
            min4,min5 = num,min4
        elif min4 <= num < min5:
            min5 = num
        else:
            pass
    return min1,min2,min3,min4,min5

s = str(input())
k = int(input())
len_s = len(s)
dict_s = {}
for i in range(len_s):
    for j in range(i,len_s):
        try:
            dict_s[s[i:j+1]] += 1
        except KeyError:
            dict_s[s[i:j+1]] = 1
list_ans = []
for key in dict_s.keys():
    list_ans.append(key)
print(min5(list_ans)[k-1])

Submission status: Time Limit Exceeded

Solution code:
s = str(input())
k = int(input())
len_s = len(s)
dict_s = {}
for i in range(len_s):
    for j in range(i,len_s):
        try:
            dict_s[s[i:j+1]] += 1
        except KeyError:
            dict_s[s[i:j+1]] = 1
list_ans = []
for key in dict_s.keys():
    list_ans.append(key)
list_ans.sort()
print(list_ans[k-1])

Submission status: Time Limit Exceeded

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

se=set()
for i in range(len(s)):
	for j in range(i,len(s)):
		se.add(s[i:j+1])
print(sorted(list(se))[k-1])

Submission status: Time Limit Exceeded

Solution code:
s  = input()

k = int(input())
l = ['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']
x = [0] * 26 

for i in range(len(s)):
    op = ord(s[i]) - ord("a")
    if x[op] == 0 :
        x[op] = [i]
    else:
        x[op].append(i)     

t =  0
g = 0
q  = set()
flag = 0 
while t <k :
    if x[g]!= 0 :
        for i in x[g]:
            r = "" 
            for u in range(i , len(s)):
                r += s[u]
                if not( r in  q):
                    t+=1
                    q.add(r)
    g+=1
print(sorted(q)[k-1])

Submission status: Time Limit Exceeded

Solution code:
s  = input()

k = int(input())
l = []
x = [0] * 26 

for i in  range(97 , 123):
    l.append(chr(i))
for i in range(len(s)):
    if x[ord(s[i]) - ord("a")] == 0 :
        x[ord(s[i]) - ord("a")] = [i]
    else:
        x[ord(s[i]) - ord("a")].append(i)     

t =  0
g = 0
q  = set()
flag = 0 
while t <k :
    if x[g]!= 0 :
        for i in x[g]:
            r = "" 
            for u in range(i , len(s)):
                r += s[u]
                if not( r in  q):
                    t+=1
                    q.add(r)
    g+=1
print(sorted(q)[k-1])

Submission status: Time Limit Exceeded

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

for i in range(len(s)):
    for j in range(i,len(s)):
        st.add(s[i:j+1])
print(sorted(list(st))[K-1])

Submission status: Time Limit Exceeded

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

substring = ''
for i in range(len(s)):
    for j in range(i,len(s)):
        substring += s[i:j+1] + ','
L = sorted(set(substring.split(',')[:-1]))
print(L[K-1])

Submission status: Time Limit Exceeded

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

sub = set()
for i in range(len(S)):
    for j in range(i,len(S)):
        sub.add(S[i:j+1])
m=list(sub)
m.sort()
print(m[K-1])

Submission status: Time Limit Exceeded

Solution code:
def getinputdata():

    # 配列初期化
    array_result = []
    
    data = input()
    
    array_result.append(data.split(" "))

    flg = 1

    try:

        while flg:

            data = input()

            if(data != ""):
                
                array_result.append(data.split(" "))

                flg = 1

            else:

                flg = 0
    finally:

        return array_result

arr_data = getinputdata()

s = arr_data[0][0]
k = int(arr_data[1][0])

s1=set()
for i in range(0,len(s)):
    
    for j in range(i+1,len(s)+1):

        s1.add(s[i:j])
        
list01=sorted(list(s1))

print(list01[k-1])

Submission status: Time Limit Exceeded

Solution code:
str = raw_input()
index = input()-1

dic = []
for i in range(0,len(str)+1):
    for j in range(0,len(str)-i):
        
        if str[j:j+i+1] not in dic:
            if len(dic)< 5 or dic[4] > str[j:j+i+1]:
                dic.append(str[j:j+i+1])
                dic.sort()
                dic = dic[:5]
print dic[index]

Submission status: Time Limit Exceeded

Solution code:
str = raw_input()
index = input()-1
dic = []
for i in range(0,len(str)+1):
    for j in range(0,len(str)-i):
        if str[j:j+i+1] not in dic:
            dic.append(str[j:j+i+1])
dic.sort()
print dic[index]

Submission status: Time Limit Exceeded

Solution code:
s = input()
K = int(input())
# substrings = {}
substrings = []
for i in range(1,len(s)+1):
    for j in range(0,len(s)):
        if s[j:j+i] not in substrings:
            # substrings[s[j:j+1]] = True
            substrings.append(s[j:j+i])
print(sorted(substrings)[K-1])

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy
import itertools


def read():
    return int(input())


def readmap():
    return map(int, input().split())


def readlist():
    return list(map(int, input().split()))


S = input()
K = read()

substring = set()
for k in range(1, max(K, len(S))+1):
    for i in range(len(S)-k+1):
        substring.add(S[i:i+k])

sub = sorted(list(substring))
print(sub[K-1])

Submission status: Time Limit Exceeded

Solution code:
substrs = set()
string = input()
k = int(input())

def solve(string):
	if len(string) == 0:
		return
	if string in substrs:
		return
	substrs.add(string)
	for i in range(1,len(string)+1):
		solve(string[:i])
	solve(string[1:])

solve(string)
substrs = sorted(list(substrs))
for i,s in enumerate(substrs):
	if i == k-1:
		print(s)
		break

Submission status: Time Limit Exceeded

Solution code:
original = str(input())
num = int(input())
string = list(original)
row = len(string)
ans = []
for i in range(1,row):
    for j in range(0,row-i+1):
        buf = ''
        for k in range(0,i):
            buf += string[j+k]
        if(buf not in ans):
            ans.append(buf)
ans.append(original)
ans = sorted(ans)
print(ans[num-1])

Submission status: Time Limit Exceeded

Solution code:
original = str(input())
num = int(input())
string = list(original)
row = len(string)
ans = []
for i in range(1,row):
    for j in range(0,row-i+1):
        buf = ''
        for k in range(0,i):
            buf += string[j+k]
        ans.append(buf)
ans.append(original)
ans = sorted(set(ans), key=ans.index)
ans = sorted(ans)
print(ans[num-1])

Submission status: Time Limit Exceeded

Solution code:
S = input()
K = int(input())
a = []
def merge2(a, b):
    c = []
    ia = 0
    ib = 0
    while True:
        if ia >= len(a):
            c += b[ib:]
            break
        elif ib >= len(b):
            c += a[ia:]
            break
        elif a[ia] < b[ib]:
            c.append(a[ia])
            ia = ia+1
        else:
            c.append(b[ib])
            ib = ib+1
    return c
for i in range(len(S)):
    a2 =[]
    for j in range(i+1,len(S)+1):
        a2.append(S[i:j])
    a.append(a2)
a.sort(key=lambda x: x[0])
i = 0
while True:
    if len(a) >1 and a[0][0] == a[1][0]:
        a[1] = merge2(a[0],a[1])
        del a[0]
    else:
        b = a.pop(0)
        b = sorted(set(b),key=b.index)
        if len(b) < K:
            K -= len(b)
        else:
            print(b[K-1])
            break

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Contents   : AtCoder Regular Contest C問題
Author     : KitauraHiromi
LastUpdate : 20180517
Since      : 20180517
"""

def duplicate(substr, strs):
    for str in strs:
        if str[:len(substr)] == substr:
            return True
    return False

def head_char(substrs, k):
    dict = {}
    for i in range(len(substrs)):
        dict[substrs[i][0]] = 0
    for i in range(len(substrs)):
        if not duplicate(substrs[i], substrs[:i]):
            dict[substrs[i][0]] += len(substrs[i])
    sum = 0
    pre_sum = 0
    pre_alph = ""
    for alph in sorted(dict.keys()):
        if sum > k:
            return (pre_alph, pre_sum)
        pre_sum = sum
        pre_alph = alph
        sum += dict[alph]
    return (pre_alph, pre_sum)

def find_substring(substrs, K, ret):
    # print("K", K, "ret", ret)
    if K <= 0:
        return ret
    head, k = head_char(substrs, K-1)
    # print("head:", head)
    idxes = [pos for pos, substr in enumerate(substrs) if substr[0] == head]
    new_substrs = [substrs[idx][1:] for idx in idxes if substrs[idx][1:] != ""]
    # print("new_substrs", new_substrs)
    # print(new_substrs, K-k)
    return find_substring(new_substrs, K-k-1, ret+head)

s = input()
K = int(input())
substrs = [s[i:] for i in range(len(s))]
print(find_substring(substrs, K, ""))

Submission status: Time Limit Exceeded

Solution code:
import math
s=input()
k=int(input())
list1=[]
hoge=0
for i in range(len(s)):
    for j in range(i+1,len(s)+1):
        list1.append(s[i:j])

list1=list(set(list1))
strmin = 0
for i in range(len(list1)-1):
    strmin = i
    for j in range(i,len(list1)):
        if list1[i] > list1[j]:
            tmp = list1[i]
            list1[i] = list1[j]
            list1[j] = tmp
print(list1[k-1])

Submission status: Time Limit Exceeded

Solution code:
word = list(input())
order = int(input())
substrings = []

for n in range(len(word)):
    for j in range(len(word)-n):
        substrings.append(''.join(word[n:j+n+1]))

an = sorted(set(substrings))
print(an[order-1])

Submission status: Time Limit Exceeded

Solution code:
word = list(input())
order = int(input())
substrings = set()

for n in range(len(word)):
    for j in range(len(word)-n):
        substrings.add(''.join(word[n:j+n+1]))

an = sorted(substrings)
print(an[order-1])

Submission status: Time Limit Exceeded

Solution code:
def main():
    s = input()
    k = int(input())
    
    l = []
    for i in range(0, len(s)):
        for j in range(0, len(s)-i):
            sub = s[i:i+j+1]

            if sub not in l:
                l.append(sub)

    l.sort()
    
    print(l[k-1])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

s1 = []
for i in range(len(s)):
    for j in range(i + 1, len(s) + 1):
        s1.append(s[i:j])
s2 = []
for i in range(len(s1)):
    if len(s1[i]) <= 5:
        s2.append(s1[i])
s2.sort()
substring = []
i = 0
while len(substring) <= 4:
    try:
        if s2[i] not in substring:
            substring.append(s2[i])
        i = i + 1
    except:
        break
print(substring[k - 1])

Submission status: Time Limit Exceeded

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

s1 = []
for i in range(len(s)):
    for j in range(i + 1, len(s) + 1):
        s1.append(s[i:j])
s1.sort()
substring = []
i = 0
while len(substring) <= 4:
    try:
        if s1[i] not in substring:
            substring.append(s1[i])
        i = i + 1
    except:
        break
print(substring[k - 1])

Submission status: Time Limit Exceeded

Solution code:
s = str(input())
n = int(input())

cand = [s[0]]
for i in range(len(s)):
    if len(cand) == n and s[i] > cand[-1]:
        continue
    for j in range(i, len(s)):
        tmp = s[i:j+1]
        #print(i,j, tmp, cand)
        if tmp in cand:
            continue
        cand += [tmp]
        #cand = sorted(cand)
        cand.sort()
        if len(cand) > n:
            cand.pop()


print(cand.pop())

Submission status: Time Limit Exceeded

Solution code:
import math
s=input()
k=int(input())
list1=[]
hoge=0
for i in range(len(s)):
    for j in range(i+1,len(s)+1):
        list1.append(s[i:j])
li_uniq=list(set(list1))
list2=sorted(li_uniq)
print(list2[k-1])

Submission status: Time Limit Exceeded

Solution code:
s = input()
k = int(input())
long = len(s)
words = []
for i in range(long):
	for j in range(i+1, long+1):
		words.append(s[i:j])
words = set(words)
words = list(words)
words.sort()
print(words[k-1])

Submission status: Time Limit Exceeded

Solution code:
s = str(input())
n = int(input())

cand = [str(s[0])]
for i in range(len(s)):
    if len(cand) == n and s[i] > cand[-1]:
        continue
    for j in range(i, len(s)):
        tmp = str(s[i:j+1])
        #print(i,j, tmp, cand)
        if tmp in cand:
            continue
        cand += [tmp]
        cand = sorted(cand)
        if len(cand) > n:
            cand.pop()


print(cand.pop())

Submission status: Time Limit Exceeded

Solution code:
A=input()
K=int(input())
A2=list(A.strip())
A2=set(A2)
A2=list(A2)
A2.sort()
Ans=A2[0]

def solve(st,s,k,li):
  an=set(s)
  lin=0
  while len(an)<=k:
    ch=False
    for i in range(len(st)):
      if st[i]==s:
        cnt=2
        while i+cnt<=len(st) or cnt<5:
          an.add(st[i:i+cnt])
          cnt+=1
    if len(an)<K:
      lin+=1
      s=li[lin]
      an.add(s)
      cnt=2
      
  an=list(an)
  an.sort()
  return an[k-1]

if K==1:
  print(Ans)
elif len(A) < 50:
  res=set()
  for i in range(len(A)):
    for j in range(i+1,len(A)+1):
      res.add(A[i:j])
  res=list(res)
  res.sort()
  print(res[K-1])
else:
  print(solve(A,Ans,K,A2))

Submission status: Time Limit Exceeded

Solution code:
A=input()
K=int(input())
A2=list(A.strip())
A2=set(A2)
A2=list(A2)
A2.sort()
Ans=A2[0]

def solve(st,s,k,li):
  an=set(s)
  lin=0
  while len(an)<=k:
    ch=False
    for i in range(len(st)):
      if st[i]==s:
        cnt=2
        while i+cnt<=len(st) or cnt<5:
          an.add(st[i:i+cnt])
          cnt+=1
    if len(an)<K:
      lin+=1
      s=li[lin]
      an.add(s)
      cnt=2
      
  an=list(an)
  an.sort()
  return an[k-1]

if K==1:
  print(Ans)
else:
  print(solve(A,Ans,K,A2))

Submission status: Time Limit Exceeded

Solution code:
s=input()
k=int(input())
t=sorted(s)
lst=[]
l=len(s)
used=[]
frag=0
for i in range(l):
    if frag==1:
        break
    if t[i] not in used:
        for j in range(l):
            if t[i]==s[j]:
                for m in range(j+1,l+1):
                    if frag==0:
                        if s[j:m] not in lst:
                            lst.append(s[j:m]) 
        if len(lst)>k:
            frag=1
lst.sort()
print(lst[k-1])

Submission status: Time Limit Exceeded

Solution code:
s = str(raw_input())
cont = int(raw_input())
result = []
for i in range(len(s)):
    for k in range(len(s)):
        for j in range(len(s) - i):
            a = s[j:k+j+1]
            #print('a:'+str(a)+' j:'+str(j)+' k:'+str(k))
            if a in result:
                continue
            else:
                result.append(a)
result.sort()
#print(result)
print(result[cont-1])

Submission status: Time Limit Exceeded

Solution code:
s = input()
K = int(input())
l = len(s)
s2 = list(set(list(s)))
s2.sort()

dic = {}
flg = False
for i in range(len(s2)):
	for j in range(l):
		if s[j] == s2[i]:
			for k in range(1,l-j+1):
				a = s[j:j+k]
				if not a in dic:
					if K == 1:
						flg = True			
					K -= 1
					dic[a] = 1

	if flg:
		break
k = list(dic.keys())
k.sort()
print(k[K-1])

Submission status: Time Limit Exceeded

Solution code:
import math
import random
import heapq
from collections import Counter, defaultdict
from decimal import Decimal, ROUND_HALF_UP, ROUND_CEILING
from functools import lru_cache, reduce
from itertools import combinations_with_replacement, product, combinations


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


# @lru_cache(size=None)
def slv(S, K):

    if len(S) <= 50:
        d = set([])
        for i in range(len(S)):
            for j in range(i + 1, len(S) + 1):
                d.add(S[i:j])

    # print('-----')

    import bisect
    S_ = [c for c in S]
    # S_.sort()
    idxs = []

    for k in sorted(set(S_)):
        # print('k', k)
        for i in range(len(S)):
            if S[i] == k:
                idxs.append(i)
        d = []

        for i in idxs:
            # print(i)
            for j in range(i + 1, len(S) + 1):
                t = "".join(S[i:j])
                if len(d) > K and d[-1] < t:
                    break
                if t not in d:
                    bisect.insort(d, t)
                    d = d[:K]
        if len(d) >= K:
            break
    print(d)
    return sorted(d)[K - 1]


def main():
    S = read_str()
    K = read_int()
    S = [random.choice('abcdefghijklmnopqrstu') for _ in range(5000)]
    print(slv(S, K))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
s = input()
K = int(input())
dic = {}
sets = set()
for i in range(len(s)):
    sets.add(s[i])
    if s[i] not in dic:
        dic[s[i]] = [i]
    else:
        dic[s[i]].append(i)
sets = list(sets)
sets.sort()
ans = set()
c = 0
while(K > len(ans)):
    for i in dic[sets[c]]:
        for j in range(i + 1, len(s) + 1):
            ans.add(s[i:j])
    c += 1
ans = list(ans)
ans.sort()
print(ans[K - 1])

Submission status: Time Limit Exceeded

Solution code:
import math
import random
import heapq
from collections import Counter, defaultdict
from decimal import Decimal, ROUND_HALF_UP, ROUND_CEILING
from functools import lru_cache, reduce
from itertools import combinations_with_replacement, product, combinations


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


# @lru_cache(size=None)
def slv(S, K):

    if len(S) <= 50:
        d = set([])
        for i in range(len(S)):
            for j in range(i + 1, len(S) + 1):
                d.add(S[i:j])

    # print('-----')

    import bisect
    S_ = [c for c in S]
    # S_.sort()
    idxs = []

    for k in sorted(set(S_)):
        # print('k', k)
        for i in range(len(S)):
            if S[i] == k:
                idxs.append(i)
        d = []

        for i in idxs:
            # print(i)
            for j in range(i + 1, len(S) + 1):
                if len(d) > K and d[-1] < S[i:j]:
                    break
                if S[i:j] not in d:
                    bisect.insort(d, S[i:j])
                    d = d[:K]
        if len(d) >= K:
            break
    # print(d)
    return sorted(d)[K - 1]


def main():
    S = read_str()
    K = read_int()
    # S = [random.choice('abcdefghijklmnopqrstu') for _ in range(5000)]
    print(slv(S, K))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import math
import random
import heapq
from collections import Counter, defaultdict
from decimal import Decimal, ROUND_HALF_UP, ROUND_CEILING
from functools import lru_cache, reduce
from itertools import combinations_with_replacement, product, combinations


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


# @lru_cache(size=None)
def slv(S, K):

    if len(S) <= 50:
        d = set([])
        for i in range(len(S)):
            for j in range(i + 1, len(S) + 1):
                d.add(S[i:j])

    # print('-----')

    import bisect
    S_ = [c for c in S]
    # S_.sort()
    idxs = []

    for k in sorted(set(S_)):
        # print('k', k)
        for i in range(len(S)):
            if S[i] == k:
                idxs.append(i)
        d = []

        for i in idxs:
            # print(i)
            for j in range(i + 1, len(S) + 1):
                if len(d) > K and d[-1] < S[i:j]:
                    break
                if S[i:j] not in d:
                    bisect.insort(d, S[i:j])
                    d = d[:K]
        if len(d) >= K:
            break
    # print(d)
    return sorted(d)[K - 1]


def main():
    S = read_str()
    K = read_int()
    S = [random.choice('abcdefghijklmnopqrstu') for _ in range(5000)]
    print(slv(S, K))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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 = []

    if len_S == 1:
        print(input_S)
    else:
        for i in range(len_S):
            for j in range(len_S):

                s = input_S[j:j+i+1]
                lis.append(s)
        print(sorted(set(lis))[K])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

list = {}

for i in range(len(s)):
    for j in range(i + 1,len(s) + 1):
        if(s[i:j] not in list):
            list[s[i:j]] = 0

keys = sorted(list.keys())

print(keys[k - 1])

Submission status: Time Limit Exceeded

Solution code:
def get_indices_of_letter(string, letter):
    indices_of_min_letter = []
    for i, c in enumerate(string):
        if c == letter:
            indices_of_min_letter.append(i)

    return indices_of_min_letter


def solve(s, k):
    letters_in_s = sorted(set(s))

    min_letter = letters_in_s[0]
    if k == 1:
        return min_letter

    indices_of_min_letter = get_indices_of_letter(s, min_letter)

    substrings_seen = set([min_letter])

    for i in indices_of_min_letter:
        for j in xrange(i + 1, len(s) + 1):
            substrings_seen.add(s[i:j])

    if len(substrings_seen) >= k:
        return sorted(substrings_seen)[k - 1]

    second_smallest_letter = letters_in_s[1]

    substrings_seen.add(second_smallest_letter)
    if len(substrings_seen) == k:
        return second_smallest_letter

    indices_of_second_letter = get_indices_of_letter(s, second_smallest_letter)

    for i in indices_of_second_letter:
        for j in xrange(i + 1, len(s) + 1):
            substrings_seen.add(s[i:j])

    if len(substrings_seen) >= k:
        return sorted(substrings_seen)[k - 1]

    return letters_in_s[2]


s = raw_input()
k = int(raw_input())

print solve(s, k)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
import copy


def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [s] = [(input_raw[0])]
    input_raw = read_func().strip().split()
    [K] = [int(input_raw[0])]

    sub_s_list = [""]
    for i in range(K):
        min_str = "z" * 5000
        for j in range(len(s)):
            sub = ""
            for k in range(j, len(s)):
                if sub in sub_s_list:
                    sub += s[k]
                if sub not in sub_s_list and sub < min_str:
                    min_str = sub
        sub_s_list.append(min_str)
    print sub_s_list[K]
                


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import math
import random
import heapq
from collections import Counter, defaultdict
from decimal import Decimal, ROUND_HALF_UP, ROUND_CEILING
from functools import lru_cache, reduce
from itertools import combinations_with_replacement, product, combinations


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


# @lru_cache(size=None)
def slv(S, K):

    if len(S) <= 50:
        d = set([])
        for i in range(len(S)):
            for j in range(i + 1, len(S) + 1):
                d.add(S[i:j])

    # print('-----')

    import bisect
    S_ = [c for c in S]
    # S_.sort()
    idxs = []

    for k in sorted(set(S_)):
        # print('k', k)
        for i in range(len(S)):
            if S[i] == k:
                idxs.append(i)
        d = []

        for i in idxs:
            for j in range(i + 1, len(S) + 1):
                if len(d) > K and d[-1] < S[i:j]:
                    break
                if S[i:j] not in d:
                    bisect.insort(d, S[i:j])
        if len(d) > K:
            break
    # print(d)
    return sorted(d)[K - 1]


def main():
    S = read_str()
    K = read_int()
    print(slv(S, K))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import collections
import string
import heapq
s=input()
n = len(s)
k = int(input())

m = ['zzzzzzz','zzzzzzz','zzzzzzz','zzzzzzz','zzzzzzz']
subs = []
for i in range(n):
    for j in range(i+1,n+1):
        sub = s[i:j]
        if sub not in subs:
            subs.append(sub)
            subs.sort()
            subs = subs[:5]
print(subs[k-1])

Submission status: Time Limit Exceeded

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

wordset = set()
l = len(s)
for i in range(l):

    for j in range(i,l+1):
        if s[i:j]:
            wordset.add(s[i:j])

a = sorted(wordset)
print(a[k-1])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
from sys import stdin


def solve(tc):
    s = stdin.readline().strip()
    k = int(stdin.readline().strip())

    n = len(s)
    li = [list() for i in range(26)]
    for i in range(n):
        li[ord(s[i])-ord('a')].append(i)
    
    p = 0
    while len(li[p])==0:
        p += 1
    
    ans = set()
    while len(ans)<k and p<26:
        for i in range(n):
            for j in range(len(li[p])):
                b = li[p][j]
                e = min(n, li[p][j] + i + 1)
                ans.add(s[b:e])
        p += 1
    lans = list(ans)
    lans.sort()
    print(lans[k-1])
    pass


LOCAL_TEST = not __debug__
if LOCAL_TEST:
    infile = __file__.split('.')[0] + "-test.in"
    stdin = open(infile, 'r')

tcs = (int(stdin.readline().strip()) if LOCAL_TEST else 1)
tc = 1
while tc <= tcs:
    solve(tc)
    tc += 1

Submission status: Time Limit Exceeded

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

l =[]

size=len(s)

for i in range(size):
    for j in range(1,size-i+1):

        l.append(s[i:i+j])
l=list(set(l))
l.sort()
print(l[N-1])

Submission status: Time Limit Exceeded

Solution code:
s = input()
K = int(input())
sub = set()
length = len(s)
for i in range(length):
    for j in range(i + 1, length + 1):
        sub.add(s[i:j])
ans = list(sub)
ans.sort()
print(ans[K - 1])