We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Shortest and Lexicographically Smallest Beautiful String

Difficulty: Medium

Problem Description

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.

Key Insights

  • A beautiful substring must contain exactly k '1's.
  • We need to find the shortest length among all beautiful substrings.
  • Among substrings of the same length, we need to find the lexicographically smallest one.
  • A sliding window approach can be effective for counting '1's in substrings.

Space and Time Complexity

Time Complexity: O(n^2) where n is the length of the string s, as we may need to check all substrings. Space Complexity: O(1) since we are only using a fixed number of variables.

Solution

To solve the problem, we can utilize a sliding window technique combined with a brute-force approach to check all possible substrings. The algorithm works as follows:

  1. Iterate over all possible starting points of substrings in the string s.
  2. For each starting point, expand the substring while counting the number of '1's.
  3. If the count of '1's reaches k, check the length of the substring. If it's shorter than previously found substrings, update the shortest length and the lexicographically smallest substring.
  4. If there are multiple substrings of the same length, compare them lexicographically to keep the smallest one.
  5. Finally, return the smallest beautiful substring found, or an empty string if none exist.

Code Solutions

def smallestBeautifulSubstring(s: str, k: int) -> str:
    n = len(s)
    min_length = float('inf')
    result = ""

    for start in range(n):
        count_ones = 0
        for end in range(start, n):
            if s[end] == '1':
                count_ones += 1
            
            if count_ones > k:
                break
            
            if count_ones == k:
                current_substring = s[start:end + 1]
                if (end - start + 1 < min_length) or (end - start + 1 == min_length and current_substring < result):
                    min_length = end - start + 1
                    result = current_substring

    return result
← Back to All Questions