Ensure that you are logged in and have the required permissions to access the test.

Find the number

1.9

17 votes
Permutation and combination, Set, Java, Python 3, Python, Medium, Algorithms, Searching algorithm, Linear search, Java 8, String
Problem

You are given a string S of length N  . The string S consists of digits from 1-9. Consider the string indexing to be 1-based.
You need to divide the string into blocks such that the ith  block contains the elements from the index((i1)X+1) to min(N,(iX)) (both inclusive). A number is valid if it is formed by choosing exactly one digit from each block and placing the digits in the order of their block number.

For example:

If the given string is '123456789' and X=3, the blocks formed are [123], [456], [789]. Few valid numbers are 147,159,348 etc.. but 124 and 396 are invalid.

Among all the valid numbers that can be formed, your task is to determine the Kthnumber if all the unique valid numbers are sorted in ascending order.

Input format

  • First line: Three space-separated integers N,X, and K.
  • Second line: String S consisting of digits (1-9).

Output format

  • Print the Kth  valid number.

Constraints

  • 1N,X105  
  • 1K1018

Note: Value of K will always be such that answer exists.

Sample Input
10 5 10
1234567891
Sample Output
29
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

The string can be divided into 2 blocks as follows:

[12345] and [67891].

The 10th largest possible number is 29.

Contributers:
Editor Image

?