MediumSliding WindowAI interview only

Shortest And Lexicographically Smallest Beautiful String

Asked atgoogleamazonmicrosoft

01 · Problem

You are given a binary string s and a positive integer k. A substring of s is beautiful if it contains exactly k characters equal to '1'.

Among all beautiful substrings, consider only those of the shortest possible length, and return the lexicographically smallest of them. If s has no beautiful substring (fewer than k ones), return the empty string "".

02 · Examples

Example 01

Input

s = "0110101", k = 2

Output

"11"

Two 1s cannot fit in fewer than 2 characters, and "11" at indices 1-2 is the only length-2 substring with exactly two 1s.

Example 02

Input

s = "1011", k = 2

Output

"11"

Beautiful substrings of length 2 exist only as "11" (indices 2-3); "101" and longer ones are not shortest.

Example 03

Input

s = "000", k = 1

Output

""

There is no '1' at all, so no substring is beautiful.

03 · Constraints

011 <= s.length <= 100
021 <= k <= s.length
03s consists only of '0' and '1'

04 · Optimal complexity

Time: O(n^2)
Space: O(n)

05 · Two ways to work on it

Practice it alone or rehearse it as an interview.

Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.

Start a voice interview on this problem