Jobs

Interviews

Discussions

Shortest and Lexicographically Smallest Beautiful String

Medium

Amazon

4 views

Topics:

StringsTwo PointersSliding Windows

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"

Example 2:

Input: s = "1011", k = 2
Output: "11"

Example 3:

Input: s = "000", k = 1
Output: ""

Constraints:

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

Shortest and Lexicographically Smallest Beautiful String

Medium

Amazon

4 views

Topics:

StringsTwo PointersSliding Windows

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.

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"

Example 2:

Input: s = "1011", k = 2
Output: "11"

Example 3:

Input: s = "000", k = 1
Output: ""

Constraints:

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

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the length of the string `s` and the integer `k`?
What characters are allowed in the string `s`? Is it strictly limited to '0' and '1'?
If no 'beautiful' string can be formed, what should I return? An empty string, null, or throw an exception?
If multiple shortest and lexicographically smallest 'beautiful' strings exist, should I return any one of them, or is there a specific criterion to prioritize one over others (besides shortest length and lexicographical order)?
Can the input string `s` be empty, or can `k` be zero or negative?

Brute Force Solution

Approach

The brute force method for this problem involves trying every possible string within the specified length to see if it meets our criteria for being a beautiful string. We then filter these strings to only keep the beautiful ones. Finally, we find the shortest and smallest (lexicographically) one from the beautiful strings we've kept.

Here's how the algorithm would work step-by-step:

First, generate all possible strings of length at least the length of the initial string and up to the specified maximum length using only the characters 'a', 'b', and 'c'.
For each generated string, check if it is 'beautiful'. A string is beautiful if it doesn't contain any consecutive repeating substrings (for example, 'aa' or 'abaaba').
If a string is 'beautiful', store it.
After checking all possible strings, find the shortest string among all the stored beautiful strings.
If there are multiple strings with the same shortest length, find the smallest one alphabetically (lexicographically) from those.
The resulting string is the shortest and lexicographically smallest beautiful string.

Code Implementation

def shortest_and_lexicographically_smallest_beautiful_string(initial_string, max_length):
    shortest_beautiful_string = None
    min_length = len(initial_string)

    def is_beautiful(test_string):
        for substring_length in range(1, len(test_string) // 2 + 1):
            for start_index in range(len(test_string) - 2 * substring_length + 1):
                first_substring = test_string[start_index:start_index + substring_length]
                second_substring = test_string[start_index + substring_length:start_index + 2 * substring_length]
                if first_substring == second_substring:
                    return False
        return True

    def generate_strings(current_string, current_length, all_beautiful_strings):
        if current_length > max_length:
            return

        if current_length >= min_length:
            if is_beautiful(current_string):
                all_beautiful_strings.append(current_string)

        for char in ['a', 'b', 'c']:
            generate_strings(current_string + char, current_length + 1, all_beautiful_strings)

    all_beautiful_strings = []
    generate_strings("", 0, all_beautiful_strings)

    # After generating all strings, we search for the shortest
    if all_beautiful_strings:
        shortest_length = min(len(beautiful_string) for beautiful_string in all_beautiful_strings)
        shortest_beautiful_strings = [beautiful_string for beautiful_string in all_beautiful_strings if len(beautiful_string) == shortest_length]

        # If multiple strings have the same shortest length, find the lexicographically smallest
        shortest_beautiful_string = min(shortest_beautiful_strings)

    return shortest_beautiful_string

Big(O) Analysis

Time Complexity

O(3^maxLength * maxLength^2) – Generating all possible strings of length n (where n ranges from the initial string's length to maxLength) using 3 characters ('a', 'b', 'c') takes O(3^maxLength) time because there are 3 options for each position. Checking if each generated string of length maxLength is 'beautiful' requires comparing substrings, taking O(maxLength^2) time in the worst case. Therefore, the overall time complexity is O(3^maxLength * maxLength^2).

Space Complexity

O(3^M) – The algorithm generates all possible strings of length up to M, where M is the specified maximum length. Since each character can be one of 'a', 'b', or 'c', there are 3^1 + 3^2 + ... + 3^M possible strings. The algorithm then stores the beautiful strings in a data structure (likely a list or set). Therefore, the space complexity is dominated by the storage of these generated and filtered strings, leading to a space complexity of O(3^M) in the worst case, where M is the maximum length of the generated strings.

Optimal Solution

Approach

We want to find the shortest string that also comes first alphabetically and satisfies the 'beautiful' condition. To do this, we focus on fixing the fewest characters possible from the original string and ensuring our changes lead to an earlier alphabetical order if possible.

Here's how the algorithm would work step-by-step:

First, check if the original string is already 'beautiful'. If it is, we're done!
If not, start by going through the string from the beginning.
Find the first place where the 'beautiful' condition is broken. We'll need to fix this spot.
To keep the string as short as possible, we only change characters from the place where the condition is broken until the end of the string.
From that breaking point, replace the rest of the string with the smallest possible characters ('a', 'b', 'c', based on the required period) to make it 'beautiful' again.
Since we want the string to be alphabetically the smallest, when replacing characters after the break, always choose the smallest character that maintains the 'beautiful' rule.

Code Implementation

def shortest_and_lexicographically_smallest_beautiful_string(input_string, period):
    string_length = len(input_string)

    def is_beautiful(current_string, current_period):
        for i in range(current_period, len(current_string)):
            if current_string[i] == current_string[i - current_period]:
                return False
        return True

    if is_beautiful(input_string, period):
        return input_string

    for i in range(string_length):
        if i >= period and input_string[i] == input_string[i - period]:
            # Found the index where the 'beautiful' condition is broken.

            for char_code in range(ord('a'), ord('a') + period):
                replacement_char = chr(char_code)
                temp_string = list(input_string)
                temp_string[i] = replacement_char
                temp_string = "".join(temp_string)

                if i >= period and temp_string[i] == temp_string[i - period]:
                    continue

                # After finding the replacement character, 
                # build the rest of the string.
                for j in range(i + 1, string_length):
                    for next_char_code in range(ord('a'), ord('a') + period):
                        next_replacement_char = chr(next_char_code)
                        temp_string_list = list(temp_string)
                        temp_string_list[j] = next_replacement_char
                        potential_string = "".join(temp_string_list)

                        if j >= period and potential_string[j] == potential_string[j - period]:
                            continue
                        else:
                            temp_string = potential_string
                            break

                #Check if new string is beautiful before returning
                if is_beautiful(temp_string, period):
                    return temp_string

            #If no lexicographically smaller string found, reconstruct string
            temp_string = list(input_string)

            #We need to reconstruct and find the smallest lexicographical
            # beautiful string.
            for j in range(i, string_length):
                for next_char_code in range(ord('a'), ord('a') + period):
                    next_replacement_char = chr(next_char_code)
                    temp_string_list = list(input_string)
                    temp_string_list[j] = next_replacement_char
                    potential_string = "".join(temp_string_list)

                    if j >= period and potential_string[j] == potential_string[j - period]:
                        continue
                    else:
                        input_string = potential_string
                        break

            return input_string

    return input_string

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the string of length n to find the first violation of the 'beautiful' condition. After finding the breaking point, it iterates through the remaining portion of the string (in the worst case, also n) to replace characters with the smallest possible characters that satisfy the condition. Therefore, we have at most 2 iterations that depend on the length of the string. The total operations is approximately 2n which simplifies to O(n).

Space Complexity

O(1) – The algorithm modifies the string in-place. It doesn't use any auxiliary data structures like lists, arrays, or hash maps that scale with the input string's length. The space complexity is dominated by a few integer variables for loop indices and possibly a boolean to track if the string was already beautiful. Therefore, the auxiliary space used is constant, independent of the input string's length N.

Edge Cases

Case	How to Handle
Input string s is null or empty	Return an empty string or an appropriate error message as no beautiful string can be generated.
Input k is zero or negative	If k is zero, an empty string is already beautiful so return the original; if k is negative throw an IllegalArgumentException as pattern length cannot be negative.
Input string s has length less than k	Construct the lexicographically smallest beautiful string of length k using the first k characters of the alphabet.
No valid 'beautiful' string exists that's lexicographically smaller than input.	Return the smallest beautiful string of length n (same length as the original input string).
Input string s consists of all the same characters.	Find the first position where we can replace the character with the next character in the alphabet while staying within constraints of k uniqueness.
k is greater than 26 (number of lowercase English letters)	Return null or throw exception since it's impossible to have a beautiful string with more than 26 unique characters using only lowercase letters.
Large input string length leading to potential performance issues	Ensure the algorithm has at most O(n) complexity so it will scale efficiently.
Handling edge cases when you reach the end of the alphabet (z)	Backtrack and increment the previous character when 'z' is reached and constraint violated, and handle carry-over effect if necessary.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the length of the string `s` and the integer `k`?
What characters are allowed in the string `s`? Is it strictly limited to '0' and '1'?
If no 'beautiful' string can be formed, what should I return? An empty string, null, or throw an exception?
If multiple shortest and lexicographically smallest 'beautiful' strings exist, should I return any one of them, or is there a specific criterion to prioritize one over others (besides shortest length and lexicographical order)?
Can the input string `s` be empty, or can `k` be zero or negative?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, generate all possible strings of length at least the length of the initial string and up to the specified maximum length using only the characters 'a', 'b', and 'c'.
For each generated string, check if it is 'beautiful'. A string is beautiful if it doesn't contain any consecutive repeating substrings (for example, 'aa' or 'abaaba').
If a string is 'beautiful', store it.
After checking all possible strings, find the shortest string among all the stored beautiful strings.
If there are multiple strings with the same shortest length, find the smallest one alphabetically (lexicographically) from those.
The resulting string is the shortest and lexicographically smallest beautiful string.

Code Implementation

def shortest_and_lexicographically_smallest_beautiful_string(initial_string, max_length):
    shortest_beautiful_string = None
    min_length = len(initial_string)

    def is_beautiful(test_string):
        for substring_length in range(1, len(test_string) // 2 + 1):
            for start_index in range(len(test_string) - 2 * substring_length + 1):
                first_substring = test_string[start_index:start_index + substring_length]
                second_substring = test_string[start_index + substring_length:start_index + 2 * substring_length]
                if first_substring == second_substring:
                    return False
        return True

    def generate_strings(current_string, current_length, all_beautiful_strings):
        if current_length > max_length:
            return

        if current_length >= min_length:
            if is_beautiful(current_string):
                all_beautiful_strings.append(current_string)

        for char in ['a', 'b', 'c']:
            generate_strings(current_string + char, current_length + 1, all_beautiful_strings)

    all_beautiful_strings = []
    generate_strings("", 0, all_beautiful_strings)

    # After generating all strings, we search for the shortest
    if all_beautiful_strings:
        shortest_length = min(len(beautiful_string) for beautiful_string in all_beautiful_strings)
        shortest_beautiful_strings = [beautiful_string for beautiful_string in all_beautiful_strings if len(beautiful_string) == shortest_length]

        # If multiple strings have the same shortest length, find the lexicographically smallest
        shortest_beautiful_string = min(shortest_beautiful_strings)

    return shortest_beautiful_string

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, check if the original string is already 'beautiful'. If it is, we're done!
If not, start by going through the string from the beginning.
Find the first place where the 'beautiful' condition is broken. We'll need to fix this spot.
To keep the string as short as possible, we only change characters from the place where the condition is broken until the end of the string.
From that breaking point, replace the rest of the string with the smallest possible characters ('a', 'b', 'c', based on the required period) to make it 'beautiful' again.
Since we want the string to be alphabetically the smallest, when replacing characters after the break, always choose the smallest character that maintains the 'beautiful' rule.

Code Implementation

def shortest_and_lexicographically_smallest_beautiful_string(input_string, period):
    string_length = len(input_string)

    def is_beautiful(current_string, current_period):
        for i in range(current_period, len(current_string)):
            if current_string[i] == current_string[i - current_period]:
                return False
        return True

    if is_beautiful(input_string, period):
        return input_string

    for i in range(string_length):
        if i >= period and input_string[i] == input_string[i - period]:
            # Found the index where the 'beautiful' condition is broken.

            for char_code in range(ord('a'), ord('a') + period):
                replacement_char = chr(char_code)
                temp_string = list(input_string)
                temp_string[i] = replacement_char
                temp_string = "".join(temp_string)

                if i >= period and temp_string[i] == temp_string[i - period]:
                    continue

                # After finding the replacement character, 
                # build the rest of the string.
                for j in range(i + 1, string_length):
                    for next_char_code in range(ord('a'), ord('a') + period):
                        next_replacement_char = chr(next_char_code)
                        temp_string_list = list(temp_string)
                        temp_string_list[j] = next_replacement_char
                        potential_string = "".join(temp_string_list)

                        if j >= period and potential_string[j] == potential_string[j - period]:
                            continue
                        else:
                            temp_string = potential_string
                            break

                #Check if new string is beautiful before returning
                if is_beautiful(temp_string, period):
                    return temp_string

            #If no lexicographically smaller string found, reconstruct string
            temp_string = list(input_string)

            #We need to reconstruct and find the smallest lexicographical
            # beautiful string.
            for j in range(i, string_length):
                for next_char_code in range(ord('a'), ord('a') + period):
                    next_replacement_char = chr(next_char_code)
                    temp_string_list = list(input_string)
                    temp_string_list[j] = next_replacement_char
                    potential_string = "".join(temp_string_list)

                    if j >= period and potential_string[j] == potential_string[j - period]:
                        continue
                    else:
                        input_string = potential_string
                        break

            return input_string

    return input_string

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Input string s is null or empty	Return an empty string or an appropriate error message as no beautiful string can be generated.
Input k is zero or negative	If k is zero, an empty string is already beautiful so return the original; if k is negative throw an IllegalArgumentException as pattern length cannot be negative.
Input string s has length less than k	Construct the lexicographically smallest beautiful string of length k using the first k characters of the alphabet.
No valid 'beautiful' string exists that's lexicographically smaller than input.	Return the smallest beautiful string of length n (same length as the original input string).
Input string s consists of all the same characters.	Find the first position where we can replace the character with the next character in the alphabet while staying within constraints of k uniqueness.
k is greater than 26 (number of lowercase English letters)	Return null or throw exception since it's impossible to have a beautiful string with more than 26 unique characters using only lowercase letters.
Large input string length leading to potential performance issues	Ensure the algorithm has at most O(n) complexity so it will scale efficiently.
Handling edge cases when you reach the end of the alphabet (z)	Backtrack and increment the previous character when 'z' is reached and constraint violated, and handle carry-over effect if necessary.