FastPrepFastPrep
Problem Brief

K Smallest Substring

FULLTIMEOA

There is a string input_str consisting of characters '0' and '1' only and an integer k. Find a substring of string input_str such that:

  • The number of '1's is equal to k
  • It has the smallest length
  • It is lexicographically smallest

    • Note: It is guaranteed that answer always exists.

    Function Description

    Complete the function getSubstring in the editor below.

    getSubstring has the following parameters:

    • string input_str: a string that consists of '0' and '1'
    • int k: the number of '1's in the answer

    Returns

    string: the substring that meets the given conditions

    1Example 1

    Input
    input_str = "0101101", k = 3
    Output
    "1011"
    Explanation

    Some of the possible substrings following the first condition:

    • "01011"
    • "1101"
    • "1011"

    The substring that is smallest in length and lexicographically smallest is "1011".

    It can be proven that there is no other substring that is smaller than "1011" in length and lexicographic order. Hence the answer is "1011".

    Constraints

    Limits and guarantees your solution can rely on.

  • 1 ≤ k ≤ length of s ≤ 10^3
  • s[i] is in the set {'0', '1'}
  • The number of '1' characters in string input_str is always greater than or equal to k.
    • public String getSubstring(String input_str, int k) {
  // write your code here
}
    Input

    input_str

    "0101101"

    k

    3

    Output

    "1011"

    Sign in to submit your solution.