Get Substring
Wells Fargo● MediumOAProblem statement
There is a string input_str consisting of characters '0' and '1' only and an integer k. Find a substring of 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
getSubstring(input_str: String, k: int) → String
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
Examples
Example 1
input_str = "0101101"k = 3return = "1011"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
- 1 ≤
k≤ length ofinput_str≤ 10^3 input_str[i]is in the set {'0', '1'}- The number of '1' characters in string
input_stris always greater than or equal tok.