Shortest and Lexicographically Smallest Beautiful String

Brute Force Approach

1. Generate all substrings: Iterate through all possible substrings of the given string s.
2. Check if beautiful: For each substring, count the number of 1s. If the count equals k, the substring is beautiful.
3. Find the shortest length: Keep track of the minimum length among all beautiful substrings.
4. Find the lexicographically smallest: Among all beautiful substrings with the minimum length, find the lexicographically smallest one.

Code (Python)

def shortest_beautiful_substring_brute_force(s, k):
    n = len(s)
    min_len = float('inf')
    result = ""

    for i in range(n):
        for j in range(i, n):
            sub = s[i:j+1]
            ones = sub.count('1')

            if ones == k:
                if len(sub) < min_len:
                    min_len = len(sub)
                    result = sub
                elif len(sub) == min_len and sub < result:
                    result = sub

    return result

• Time Complexity: O(n^3) because we generate O(n^2) substrings and counting ones takes O(n).
• Space Complexity: O(n) because we store substrings of up to length n.

Optimal Solution: Sliding Window

A sliding window approach can improve efficiency by avoiding redundant calculations.

1. Expand the window: Start with an empty window and expand it to the right.
2. Count ones: Maintain a count of 1s within the window.
3. Shrink the window: If the count of 1s exceeds k, shrink the window from the left until the count is equal to k.
4. Update minimum length and lexicographical order: If the count equals k, update the minimum length and lexicographically smallest substring.

Edge Cases

• If no beautiful substring exists, return an empty string.
• Handle cases where k is greater than the number of 1s in s.

Code (Python)

def shortest_beautiful_substring(s, k):
    n = len(s)
    min_len = float('inf')
    result = ""
    left = 0
    ones = 0

    for right in range(n):
        if s[right] == '1':
            ones += 1

        while ones > k:
            if s[left] == '1':
                ones -= 1
            left += 1

        if ones == k:
            length = right - left + 1
            sub = s[left:right+1]

            if length < min_len:
                min_len = length
                result = sub
            elif length == min_len and sub < result:
                result = sub

    return result

• Time Complexity: O(n) because each character in s is visited at most twice (once by the right pointer and once by the left pointer).
• Space Complexity: O(n) because we store at most one substring of length n.