Shortest and Lexicographically Smallest Beautiful String

You are given a binary string s and a positive integer k.

A substring of s is beautiful if the number of 1's in it is exactly k.

Let len be the length of the shortest beautiful substring.

Return the lexicographically smallest beautiful substring of string s with length equal to len. If s doesn't contain a beautiful substring, return an empty string.

A string a is lexicographically larger than a string b of the same length if, in the first position where a and b differ, a has a character strictly larger than the corresponding character in b.

Example 1
Inputs = "100011001", k = 3
Output"11001"
The length of the shortest beautiful substring is 5, and the lexicographically smallest beautiful substring with length 5 is "11001".
Example 2
Inputs = "1011", k = 2
Output"11"
The length of the shortest beautiful substring is 2, and the lexicographically smallest beautiful substring with length 2 is "11".

Constraints

  • 1 <= s.length <= 100
  • 1 <= k <= s.length

Asked at 3 companies

</>

Your Solution

(Ctrl/Cmd + Enter)

Switching Language

Loading template...

Loading...

Sign in to save your progress

AI code evaluation

Get a correctness verdict, missed edge cases, and complexity analysis of your solution.

Sign in to evaluate