Lexicographically Smallest Beautiful String Interview Question for Google

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.

def solve():
    s = input()
    k = int(input())
    n = len(s)

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

    def find_next_beautiful(current_string, index, k):
        if index == -1:
            return ""

        current_char = current_string[index]
        
        for i in range(ord(current_char) + 1, ord('a') + k):
            new_char = chr(i)
            temp_string = list(current_string)
            temp_string[index] = new_char
            temp_string = "".join(temp_string)

            prefix = temp_string[:index+1]

            if len(prefix) >= 2 and prefix[-1] == prefix[-2]:
                continue
            
            suffix = ''
            possible = True
            for j in range(index + 1, n):
                found = False
                for char_code in range(ord('a'), ord('a') + k):
                    potential_char = chr(char_code)
                    if j >= 1 and potential_char == temp_string[j-1]:
                        continue
                    if j >= 2 and potential_char == temp_string[j-2]:
                        continue
                    suffix += potential_char
                    temp_string_list = list(temp_string)
                    temp_string_list[j] = potential_char
                    temp_string = "".join(temp_string_list)
                    found = True
                    break
                if not found:
                    possible = False
                    break

            if possible:
                return temp_string

        return find_next_beautiful(current_string, index - 1, k)
    
    result = find_next_beautiful(s, n - 1, k)
    print(result)


# Example usage (comment out when submitting to LeetCode runner)
# s = "abcz"
# k = 26
# print(find_next_beautiful(s, len(s) - 1, k))

# s = "dc"
# k = 4
# print(find_next_beautiful(s, len(s) - 1, k))

# s = "abaa"
# k = 3
# print(find_next_beautiful(s, len(s) - 1, k))


solve()

Explanation:

The solve function takes the beautiful string s and the integer k as input and returns the lexicographically smallest beautiful string larger than s. The core logic is in the find_next_beautiful function, which recursively tries to find a larger beautiful string.

is_beautiful(st) function:
- This helper function checks if a given string st is beautiful. A string is considered beautiful if it doesn't contain any palindrome substring of length 2 or more.
find_next_beautiful(current_string, index, k) function:
- This function recursively searches for the next beautiful string larger than the given string current_string. It starts from the rightmost character of the string (index n-1).
- Base case: If index becomes -1, it means we have exhausted all possibilities, and no such larger beautiful string exists, so it returns an empty string.
- It iterates through characters greater than the character at the current index current_string[index], up to the k-th character of the alphabet.
- For each possible character new_char, it replaces the character at the current index in current_string with new_char. It then checks if the prefix of the modified string is still beautiful.
- If the prefix is beautiful, it attempts to construct the rest of the string (suffix) such that the entire string remains beautiful. It does this by iterating through all remaining positions and choosing the smallest possible character that doesn't create a palindrome of length 2 or more.
- If it successfully constructs the entire string, it returns the resulting string.
- If it fails to find a valid character for any position in the suffix, it means the current new_char at the given index doesn't lead to a valid solution. It continues with the next possible new_char.
- If no valid new_char is found at the current index, it recursively calls find_next_beautiful for the previous index.

Big(O) Run-time Analysis

The run-time complexity of the given algorithm is difficult to precisely determine due to the recursive nature and the constraints related to constructing a valid beautiful string. However, we can analyze it in terms of the input size n (length of the string) and k (the number of possible characters). Here is a breakdown:

The find_next_beautiful function recursively explores possible characters at each index of the string s.
In the worst case, for each index, it may iterate through all k characters.
For each character, it attempts to construct the remaining part of the string while maintaining the beautiful property. This involves checking for palindromes of length 2, which takes O(1) time per character, and then O(n) for potentially filling out the rest of the suffix
Therefore, the overall run-time complexity can be approximated as O(n * k * (n)), where n is for filling out suffix.

Big(O) Space Usage Analysis

The space complexity of the algorithm can be analyzed as follows:

The algorithm uses recursion, so the call stack will take O(n) space in the worst case.
The temporary string temp_string is used to construct the new string. The size of temp_string is O(n).
Therefore, the overall space complexity is O(n).

Edge Cases

Input string is already the largest possible beautiful string: In this case, the algorithm will return an empty string.
k is small: When k is small (e.g., k=4), the constraints on beautiful strings become more restrictive, and it might be harder to find a valid next beautiful string.
Long input string: For very long input strings, the recursive calls might take a considerable amount of time. The algorithm is optimized to avoid exploring unnecessary branches, but it can still be slow in the worst case.