1. Question
You are given a string of lowercase English letters.
A substring of the string is a contiguous sequence of characters between two positions in the string.
If the two positions are the same, the substring has length 1.
For example, all substrings of the string "love" are l, o, v, e, lo, ov, ve, lov, ove, love.
Another example, the substrings of the string "food" are f, o, d, fo, oo, od, foo, ood, food. Note that the same substring "o" appears twice, but we remove duplicates.
Consider sorting this string in lexicographic order.
Compare two strings from left to right, and the one with the first different letter in alphabetical order comes first when the first different letter is found.
If one string ends before the other string before finding a different letter, then the shorter string comes first.
The following figure is an example of sorting in lexicographic order (not related to the problem-solving example).
For the example strings "love" and "food", sorted in lexicographic order, the result is as follows:
Order Substring of love Substring of food
1 e d
2 l f
3 lo fo
4 lov foo
5 love food
6 o o
7 ov od
8 ove oo
9 v ood
10 ve Write a program that takes a string and an integer K, and outputs the substring that comes in lexicographic order Kth.
Follow the following input and output conditions:
[Input]
The first line is the number of total test cases.
Each test case consists of a line containing an integer K, followed by a line containing a string of lowercase English letters.
The length of the string is at most 400.
[Output]
For each test case, print "#C" on the first line, where C is the case number.
On the same line, print the lexicographically Kth substring, separated by a single space.
If there is no Kth substring, print "none".
2. Thoughts
Make all possibilities.
Remove duplicates using set()
sort using list at last, then print kth element
3. Tips learned
4. My solution
import sys
sys.stdin = open("input.txt", "r")
def get_index_string(num, given_string):
dictionary = set()
for split_num in range(len(given_string) + 1):
for i in range(len(given_string) - split_num + 1):
dictionary.add(given_string[i : i + split_num])
return sorted(list(dictionary))[num]
T = int(input())
for test_case in range(1, T + 1):
index_num = int(input())
given_string = input()
index_string = get_index_string(index_num, given_string)
print(f"#{test_case} {index_string}")
5. AI Solution and Improvements
