K Smallest Substring (Shortest Substring With Exactly K Ones)

Reported in interviews at Akuna Capital

Problem statement

You are given a binary string input_str (characters '0' and '1' only) and an integer $k$. Return the substring of input_str that

  1. contains exactly $k$ characters equal to '1';
  2. among all such substrings, has the smallest length;
  3. among those of smallest length, is lexicographically smallest.

An answer is guaranteed to exist: input_str contains at least $k$ ones. Constraints: $1 \le k \le |\text{input\_str}| \le 10^3$. Implement getSubstring(input_str, k) -> str.

Example: input_str = "0101101", $k = 3$. Substrings with exactly three ones include "01011", "1101", "1011", "01101" and "10110". The shortest of them have length 4: "1101" and "1011". The lexicographically smaller of the two is "1011", so the answer is "1011".

Show hint

Which characters can sit at the two ends of a shortest substring that still has the required count?

Relevant roles: ML Engineer, Forward Deployed Engineer and AI Engineer.

Related free problems