Shortest Substring with Exactly K Ones
Updated
Problem statement
You are given a binary string s and a positive integer k. A substring of s is a run of consecutive characters in it.
Among all substrings of s that contain exactly k characters '1', look only at the shortest ones. Return the smallest of these in dictionary order. If no substring contains exactly k ones, return the empty string "".
Length is compared first: a longer substring is never the answer, even if it would come first in dictionary order. For two strings of the same length, dictionary order means the one with '0' at the first position where they differ is smaller.
Function
shortestSubstringWithKOnes(s: String, k: int) → StringExamples
Example 1
s = "1101001011"k = 3return = "1011"The ones are at positions 0, 1, 3, 6, 8 and 9. A substring with exactly three ones is shortest when it starts and ends on a one, so the candidates are "1101" (positions 0 to 3), "101001" (1 to 6), "100101" (3 to 8) and "1011" (6 to 9). The shortest length is 4, shared by "1101" and "1011". They first differ at their second character, where "1011" has the 0, so it is smaller.
Example 2
s = "100011"k = 2return = "11""10001" has two ones and would come first in dictionary order, but it has length 5. "11" has two ones and length 2, which is the shortest possible, so the answer is "11". Length is compared first.
Example 3
s = "010"k = 2return = ""The string has only one '1', so no substring has exactly two ones. Return the empty string.
Constraints
1 <= s.length <= 10^4s[i]is either'0'or'1'.1 <= k <= s.length
More Expedia Onsite Interview questions
- Scramble StringONSITE INTERVIEW · Seen Sep 2026
- Smallest Sufficient TeamONSITE INTERVIEW · Seen Sep 2026
- Check Anagram Pairs Index by IndexONSITE INTERVIEW · Seen Oct 2025
- Fresh Oranges Left After Rotting StopsONSITE INTERVIEW · Seen Oct 2025
- Longest Increasing SubsequenceONSITE INTERVIEW · Seen Oct 2025
- Lowest Common Ancestor with Repeated and Missing ValuesONSITE INTERVIEW · Seen Oct 2025
- Middle Element of a Linked ListONSITE INTERVIEW · Seen Nov 2024
- Minimum in a Rotated Sorted ArrayONSITE INTERVIEW · Seen Sep 2024
- Mirror Image Binary TreesONSITE INTERVIEW · Seen Sep 2024
- Maximum Supplier ProfitONSITE INTERVIEW · Seen Aug 2024
Similar questions at other companies
- Longest Substring Without Repeating CharactersSalesforce · ONSITE INTERVIEWSalesforce interview questions
- Longest Substring Without Repeating CharactersMicrosoft · ONSITE INTERVIEWMicrosoft interview questions
- Shortest Deletion for Distinct CharactersOracle · ONSITE INTERVIEWOracle interview questions
- Longest Substring Without Repeating CharactersGoogle · ONSITE INTERVIEWGoogle interview questions
- Maximize Consecutive Equal AnswersAmazon · ONSITE INTERVIEW
- Longest Repeating Character ReplacementDigitalOcean · ONSITE INTERVIEWDigitalOcean interview questions
- Longest Substring Without Repeating CharactersInfosys · ONSITE INTERVIEWInfosys interview questions
- Longest Substring Without Repeating CharactersOmnissa · ONSITE INTERVIEWOmnissa interview questions
- Longest Substring with At Most K Distinct CharactersGoldman Sachs · ONSITE INTERVIEWGoldman Sachs interview questions
- Longest Substring Without Repeating CharactersBloomberg LP · PHONE SCREEN · ONSITE INTERVIEWBloomberg LP interview questions