FastPrepShortest Substring with Exactly K Ones
Problems/Shortest Substring with Exactly K Ones

Shortest Substring with Exactly K Ones

Expedia logoExpedia● MediumINTERNONSITE INTERVIEW

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: A 2025 Expedia software engineering intern candidate, interviewed when Expedia visited their campus, got this in the second of two interviews held there. The report gives only a one-line title for this question, plus a link to a known problem about binary strings and substrings with a fixed number of ones.

Here, the task follows that link. Look only at substrings of the given string, keep the shortest ones with exactly k ones, and return the first of those in dictionary order. Return an empty string when the string has fewer than k ones. The title alone could also be read as building a brand-new binary string, but the link points to the substring task, so that reading is not used. The limits (strings up to 10^4 characters) and the examples are our choices.

Our version is about 85% the same as the reported question.

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) → String

Examples

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^4
  • s[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

Interview reports that mention this question

  • Expedia SWE Intern Final Round: 126 Experiences (Part 1 of 6)
  • Expedia New Grad SDE Interviews: 20 Experiences (Part 1 of 3)

Expedia interview experiences

  • Expedia Intern Final Round in 2021: 28 Experiences (Part 4 of 6)
  • Expedia Intern Finals Before 2020: 14 Experiences (Part 6 of 6)
  • Expedia Intern Final Round in 2020: 24 Experiences (Part 5 of 6)
  • Expedia Intern Final Round in 2022: 15 Experiences (Part 3 of 6)
All Expedia interview questionsSee Expedia hiring insights
Saved
class Solution {
    public String shortestSubstringWithKOnes(String s, int k) {
        // Write your code here.
    }
}
Checking account…