Lexicographically Smallest Beautiful String

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.

def find_beautiful_string(s: str, k: int) -> str:
    n = len(s)
    chars = [chr(ord('a') + i) for i in range(k)]

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

    def increment_string(index: int) -> str:
        if index < 0:
            return ""
        
        for char in chars:
            temp_s = list(s)
            temp_s[index] = char
            temp_str = "".join(temp_s)

            if is_beautiful(temp_str):
                if temp_str > s:
                  return temp_str
        
        s_list = list(s)
        s_list[index] = 'a'
        s = "".join(s_list)
        return increment_string(index-1)

    result = increment_string(n-1)

    if not result:
        return ""

    # Ensure that the incremented string consists of only the first k letters
    if not all(c in chars for c in result):
      return ""

    # Ensure that the incremented string is beautiful
    if not is_beautiful(result):
      return ""

    return result


# Example usage:
s = "abcz"
k = 26
print(find_beautiful_string(s, k))

s = "dc"
k = 4
print(find_beautiful_string(s, k))

s = "aba"
k = 3
print(find_beautiful_string(s, k))

s = "abca"
k = 3
print(find_beautiful_string(s, k))

Explanation:

1. Function Definition: The code defines a function find_beautiful_string(s, k) that takes a beautiful string s and an integer k as input.
2. Character Set: It generates a list of characters chars containing the first k lowercase English letters.
3. is_beautiful Helper Function: A helper function is_beautiful(test_str) checks if a given string test_str is beautiful according to the problem definition (i.e., it consists of the first k letters and contains no palindrome substring of length 2 or more).
4. increment_string Helper Function:
   • The core logic resides in the recursive helper function increment_string(index). This function attempts to increment the character at the given index to find the next lexicographically larger beautiful string.
   • It iterates through the available characters (chars) and tries replacing the character at the current index with each character from chars.
   • If the resulting string (temp_str) is beautiful and lexicographically larger than the original string s, the function returns it.
   • If no suitable character is found at the current index, it resets the character at that index to 'a' and recursively calls increment_string for the previous index (index - 1). This is essentially handling the carry-over when incrementing a number.
   • If the index goes below 0, it means that it's not possible to generate a larger beautiful string, so it returns an empty string.
5. Main Logic:
   • The function calls increment_string(n-1) to start incrementing from the last character of the input string s.
   • After potentially finding a result from the recursive calls, there are some crucial validation steps:
     • It checks if the returned result is empty, and returns an empty string if that's the case, signifying that no solution was found.
     • It ensures that the result string comprises only the first k letters.
     • It verifies that the result string adheres to the 'beautiful' constraint using is_beautiful(result).
6. Return Value: The function returns the lexicographically smallest beautiful string that is larger than s, or an empty string if no such string exists.

Time and Space Complexity

Time Complexity:

The worst-case time complexity is O(n * k), where n is the length of the string and k is the number of allowed characters. In the worst case, the increment_string function might have to explore all possible characters at each position of the string. This occurs when the initial characters need to be rolled over multiple times. Specifically, the increment_string function has a loop that iterates k times, and the depth of the recursion can be at most n. So, it's O(n * k).

Space Complexity:

The space complexity is primarily determined by the recursion depth of the increment_string function, which can be at most O(n) in the worst case. Additionally, temporary strings temp_str and s_list are created within the increment_string function, but their space is also bounded by O(n). Therefore, the overall space complexity is O(n).