Shortest and Lexicographically Smallest Beautiful String Interview Question for Amazon

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.

For example, "abcd" is lexicographically larger than "abcc" because the first position they differ is at the fourth character, and d is greater than c.

Example 1: Input: s = "100011001", k = 3 Output: "11001" Explanation: There are 7 beautiful substrings in this example:

The substring "100011001".
The substring "100011001".
The substring "100011001".
The substring "100011001".
The substring "100011001".
The substring "100011001".
The substring "100011001".

The length of the shortest beautiful substring is 5. The lexicographically smallest beautiful substring with length 5 is the substring "11001".

Example 2: Input: s = "1011", k = 2 Output: "11" Explanation: There are 3 beautiful substrings in this example:

The substring "1011".
The substring "1011".
The substring "1011".

The length of the shortest beautiful substring is 2. The lexicographically smallest beautiful substring with length 2 is the substring "11".

Example 3: Input: s = "000", k = 1 Output: "" Explanation: There are no beautiful substrings in this example.

def shortest_beautiful_substring(s: str, k: int) -> str:
    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 (result == "" or sub < result):
                    result = sub

    return result

# Example usage:
s = "100011001"
k = 3
print(shortest_beautiful_substring(s, k))  # Output: 11001

s = "1011"
k = 2
print(shortest_beautiful_substring(s, k))  # Output: 11

s = "000"
k = 1
print(shortest_beautiful_substring(s, k))  # Output: ""

Brute Force Solution

The brute force approach iterates through all possible substrings of the given string s, counts the number of 1s in each substring, and checks if the count equals k. If it does, the length of the substring is compared to the current minimum length found so far. If the current substring is shorter, it becomes the new shortest beautiful substring. If the lengths are equal, the lexicographically smaller substring is chosen.

Optimal Solution

While the above code provides a correct solution, it can be optimized. A sliding window approach can improve efficiency. The algorithm maintains a window and expands it to the right until the number of 1s in the window equals k. Then, it shrinks the window from the left while maintaining the count of 1s equal to k. This approach avoids redundant calculations and reduces the time complexity.

def shortest_beautiful_substring_optimal(s: str, k: int) -> str:
    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:
            curr_len = right - left + 1
            curr_sub = s[left:right + 1]

            if curr_len < min_len:
                min_len = curr_len
                result = curr_sub
            elif curr_len == min_len and (result == "" or curr_sub < result):
                result = curr_sub

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

    return result

# Example usage:
s = "100011001"
k = 3
print(shortest_beautiful_substring_optimal(s, k))  # Output: 11001

s = "1011"
k = 2
print(shortest_beautiful_substring_optimal(s, k))  # Output: 11

s = "000"
k = 1
print(shortest_beautiful_substring_optimal(s, k))  # Output: ""

Big(O) Run-time Analysis

Brute Force:

The outer loop runs n times.
The inner loop runs up to n times.
Inside the inner loop, sub.count('1') takes O(n) in the worst case.
Therefore, the overall time complexity is O(n^3).

Optimal (Sliding Window):

The outer loop runs n times.
The inner while loop runs at most n times in total because left only increments.
Therefore, the overall time complexity is O(n).

Big(O) Space Usage Analysis

Brute Force:

The sub string can be at most n characters long, so it takes O(n) space.
Other variables take constant space.
Therefore, the overall space complexity is O(n).

Optimal (Sliding Window):

The curr_sub string can be at most n characters long, so it takes O(n) space.
Other variables take constant space.
Therefore, the overall space complexity is O(n).

Edge Cases

Empty String: If the input string s is empty, the algorithm should return an empty string.
k is Zero: If k is 0, the algorithm should return the shortest substring with no 1s (if it exists).
k is Larger than the Number of 1s in s: If k is larger than the total number of 1s in s, the algorithm should return an empty string.
No Beautiful Substring: If there is no substring with exactly k ones, the algorithm should return an empty string.
Large Input String: For very large strings, the sliding window approach is more efficient than the brute force method.
String with only 0s: If the string contains only 0s and k > 0, the algorithm should return an empty string.