Lexicographically Smallest Beautiful String

Hard

Amazon

5 views

Topics:

Strings

A string is beautiful if:

It consists of the first k letters of the English lowercase alphabet.
It does not contain any substring of length 2 or more which is a palindrome.

You are given a beautiful string s of length n and a positive integer k.

Return the lexicographically smallest string of length n, which is larger than s and is beautiful. If there is no such string, 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 = "abcz", k = 26
Output: "abda"
Explanation: The string "abda" is beautiful and lexicographically larger than the string "abcz".
It can be proven that there is no string that is lexicographically larger than the string "abcz", beautiful, and lexicographically smaller than the string "abda".

Example 2:

Input: s = "dc", k = 4
Output: ""
Explanation: It can be proven that there is no string that is lexicographically larger than the string "dc" and is beautiful.

Constraints:

1 <= n == s.length <= 10^5
4 <= k <= 26
s is a beautiful string.

Lexicographically Smallest Beautiful String

Hard

Amazon

5 views

Topics:

Strings

A string is beautiful if:

It consists of the first k letters of the English lowercase alphabet.
It does not contain any substring of length 2 or more which is a palindrome.

You are given a beautiful string s of length n and a positive integer k.

Return the lexicographically smallest string of length n, which is larger than s and is beautiful. If there is no such string, 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 = "abcz", k = 26
Output: "abda"
Explanation: The string "abda" is beautiful and lexicographically larger than the string "abcz".
It can be proven that there is no string that is lexicographically larger than the string "abcz", beautiful, and lexicographically smaller than the string "abda".

Example 2:

Input: s = "dc", k = 4
Output: ""
Explanation: It can be proven that there is no string that is lexicographically larger than the string "dc" and is beautiful.

Constraints:

1 <= n == s.length <= 10^5
4 <= k <= 26
s is a beautiful string.

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 is the maximum length of the input string `s` and what characters are allowed in the string (e.g., only lowercase English letters)?
If it's impossible to make the string 'beautiful' according to the rules, what should my function return (e.g., null, an empty string, or throw an exception)?
Could you please clarify what is meant by 'beautiful'? Does it mean no palindrome of length 2 or more?
If multiple lexicographically smallest beautiful strings exist, should I return any one of them?
Can `k` be larger than the length of the input string `s`?

Brute Force Solution

Approach

The brute force method tries every possible string that could be the answer. It checks each one to see if it meets the 'beautiful' requirement and picks the smallest one when sorted alphabetically.

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

Start by generating all possible strings of the same length as the original string.
For each generated string, check if it meets the 'beautiful' criteria. This means checking that no two adjacent characters are the same and no three adjacent characters are in alphabetical order.
If a generated string is 'beautiful', compare it to the smallest 'beautiful' string found so far.
If the current 'beautiful' string is smaller alphabetically than the smallest found so far, replace the smallest found so far with the current string.
Repeat these steps for every possible generated string.
After checking all possible strings, the smallest 'beautiful' string found will be the answer.

Code Implementation

def find_lexicographically_smallest_beautiful_string_brute_force(string_value, forbidden_length):
    string_length = len(string_value)
    smallest_beautiful_string = None

    def is_beautiful(test_string):
        for index in range(len(test_string) - 1):
            if test_string[index] == test_string[index + 1]:
                return False
        for index in range(len(test_string) - 2):
            if ord(test_string[index]) + 1 == ord(test_string[index + 1]) and \
               ord(test_string[index + 1]) + 1 == ord(test_string[index + 2]):
                return False
        return True

    def generate_all_strings(current_string, current_length):
        nonlocal smallest_beautiful_string

        if current_length == string_length:
            
            if is_beautiful(current_string):
                # Check if the string is lexicographically smaller.
                if smallest_beautiful_string is None or current_string < smallest_beautiful_string:
                    smallest_beautiful_string = current_string
            return

        for character_code in range(ord('a'), ord('a') + forbidden_length):

            generate_all_strings(current_string + chr(character_code), current_length + 1)

    # Initiate string generation
    generate_all_strings("", 0)
    
    # Return smallest beautiful string found
    return smallest_beautiful_string

Big(O) Analysis

Time Complexity

O(k^n) – The algorithm generates all possible strings of length n, where each character can be one of k possible characters (in this problem, k would be the number of distinct characters allowed). Generating all possible strings takes O(k^n) time. For each generated string, the algorithm checks if it is 'beautiful'. This check involves iterating through the string to check adjacent and sets of three adjacent characters, which takes O(n) time. Since we have to check O(k^n) strings, and each check costs O(n), the overall runtime is O(n * k^n). However, the dominating term is the generation of the strings, so the time complexity is approximately O(k^n).

Space Complexity

O(N) – The brute force solution described generates and stores potential 'beautiful' strings of the same length as the input string. Each generated string, potentially of length N (where N is the length of the original string), is stored in memory for checking. Additionally, the solution maintains a variable to hold the smallest 'beautiful' string found so far, which could also be of length N in the worst case. Therefore, the auxiliary space required grows linearly with the length of the input string, leading to a space complexity of O(N).

Optimal Solution

Approach

The goal is to find the smallest 'beautiful' string possible, based on the alphabet size and forbidden substrings. We'll start from the end and work backwards, making sure to only explore options that are lexicographically smaller and that don't create any bad substrings.

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

Start by looking at the last character in the string.
Try replacing the last character with the next letter in the alphabet.
If replacing the letter doesn't create any forbidden pairs with the letter before it, and the new letter is smaller than any character that came later, keep the change.
If the replacement creates a forbidden pair, or the new letter isn't small enough, move on to the next letter in the alphabet and repeat.
If you tried all the letters in the alphabet and none work for the last position, go back one character and repeat the process there.
Keep doing this until you find a solution; at each step, only make replacements that lead to a 'beautiful' string, and ensure you pick the smallest available replacement.

Code Implementation

def find_smallest_beautiful_string(string_length, alphabet_size, forbidden_substring):
    result = ['a'] * string_length

    def is_beautiful(current_string):
        for i in range(len(current_string) - 1):
            if current_string[i:i+2] == forbidden_substring:
                return False
        return True

    def find_lexicographically_smallest(index):
        if index == -1:
            return ''.join(result)

        for char_code in range(ord('a'), ord('a') + alphabet_size):
            potential_char = chr(char_code)
            result[index] = potential_char

            # Before proceeding, verify no forbidden substring exists.
            if index > 0 and result[index-1] + potential_char == forbidden_substring:
                continue

            # Ensure the new char is smaller than any later characters.
            is_smaller_than_later = True
            for future_index in range(index + 1, string_length):
                if potential_char > result[future_index]:
                    is_smaller_than_later = False
                    break

            if is_smaller_than_later:

                solution = find_lexicographically_smallest(index - 1)
                if solution:
                    return solution

        # If no solution is found, backtrack.
        result[index] = 'a'
        return None

    solution = find_lexicographically_smallest(string_length - 1)
    
    if solution and is_beautiful(solution):
        return solution
    else:
        return ""

Big(O) Analysis

Time Complexity

O(n*m) – The algorithm iterates through the string from right to left, which is the dominant loop running n times, where n is the length of the input string. In each iteration, it attempts to replace the current character with the next smallest valid character from the alphabet. For each character, in the worst-case scenario, it may need to try all 'm' characters in the alphabet to find a valid replacement and also perform forbidden pair checks, so the inner operation costs O(m). Therefore, the overall time complexity is O(n*m), where n is the length of the string and m is the alphabet size.

Space Complexity

O(N) – The algorithm's space complexity primarily arises from the potential recursion depth. In the worst-case scenario, the algorithm might need to backtrack through each of the N characters of the input string when a valid replacement cannot be found, resulting in a recursion stack depth proportional to N. Thus, the auxiliary space used by the recursion stack is O(N). No other significant auxiliary data structures are used.

Edge Cases

Case	How to Handle
Empty string input	Return an empty string or an appropriate error, as an empty string cannot be modified to be 'beautiful'.
k is zero	If k is zero, the string is already beautiful if all adjacent characters are distinct; no changes are needed or possible, so return the original string or handle as an error.
String length is one	If the string length is 1, it can always be made beautiful as no adjacent characters exist; change the single character to the smallest possible character not equal to its neighbors (which is none), if k > 0.
String consisting of identical characters with k=1 and length > 1	The algorithm must correctly alternate characters to make it beautiful, for example 'aaaa' becomes 'ababa'.
Input string already lexicographically smallest beautiful string	If the input is already the smallest beautiful string (e.g., 'abcabc...' with k=3), the algorithm should return the original string.
The string cannot be modified to become beautiful given the constraints.	Return an empty string or an appropriate error if generating a beautiful string is impossible (e.g., k = 1 and string consists of repeating one character, or k is smaller than the number of distinct characters).
Large input string causing potential time limit exceed issues.	Ensure the solution is optimized for time complexity (e.g., avoid unnecessary string manipulations), and consider early termination conditions where applicable.
Input string contains characters outside the 'a' + k range	Ensure that the input characters are within the allowed range before modification, or throw an IllegalArgumentException otherwise.