FastPrepK Smallest Substring
Problems/K Smallest Substring

K Smallest Substring

Akuna Capital logoAkuna Capital● MediumFULLTIMEINTERNOA
QuestionFunctionExamplesConstraints

Problem statement

You are given a binary string input_str and an integer k.

Find a substring of input_str that satisfies all of the following conditions:

  • It contains exactly k occurrences of '1'.
  • It has the smallest possible length.
  • Among all substrings with that minimum length, it is lexicographically smallest.

It is guaranteed that an answer exists.

Function

getSubstring(input_str: String, k: int) → String

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 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.

More Akuna Capital problems

  • Delivery Management SystemOA · Seen Nov 2026
  • Count Server ReplacementsOA · Seen Nov 2026
  • Match Orders by Price and Arrival TimeOA · PHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
All Akuna Capital interview questionsSee Akuna Capital hiring insights
Saved
class Solution {
    public String getSubstring(String input_str, int k) {
      // write your code here
    }

}
Checking account…