Leetcode Problem 2904. Shortest and Lexicographically Smallest Beautiful String

2904. Shortest and Lexicographically Smallest Beautiful String

Leetcode Solutions

Sliding Window with Early Stopping

  1. Initialize variables to keep track of the current window's start index, the count of ones, the minimum length, and the result string.
  2. Iterate through the string with an index i representing the end of the current window.
  3. Expand the window by including the current character and increment the count of ones if the character is '1'.
  4. While the count of ones is greater than k, contract the window from the left by incrementing the start index and decrementing the count of ones if a '1' is removed.
  5. If the count of ones equals k, compare the current window's length and lexicographic order with the result.
  6. Update the result if the current window is shorter or lexicographically smaller with the same length.
  7. Continue until the end of the string, using early stopping if the remaining string cannot produce a shorter result.
  8. Return the result string.
UML Thumbnail

Brute Force Search

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...