2663.Lexicographically_Smallest_Beautiful_String(Hard).md

2663. Lexicographically Smallest Beautiful String (Hard)

Date and Time: Nov 4, 2024, 17:04 (EST)

Link: https://leetcode.com/problems/lexicographically-smallest-beautiful-string/

Question:

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.

Walk-through:

1. We first increment the last element by one, we can do that by increasing its ASCII code ord(s[i])+1.

2. Then we check if this updated char is within the first k characters or not by ord(s[i]) - ord('a') >= k. If the current s[i] is out of the first k characters, we reset this ith element to be a, then we decrement i -= 1 to increment the next element (its left element).

3. Next, we are checking the palindrome, if we detect a palindrome, we blindly increment current element, but don't change the index, so the code will either decrement the index or increment the index.

4. Lastly, if the while loop ends (either i < 0 or i = len(s)). If i < 0, then we know we can't find a string because we didn't finish (normal case will have i == len(s)). Otherwise, we can return the final string.

ord('a') to get Unicode from string, chr(63) to get the string from unicode.

Python Solution:

class Solution:
    def smallestBeautifulString(self, s: str, k: int) -> str:
        # Find a smallest larger string than s
        # 1. All letters consist of the first k
        # 2. no palindrome length >= 2

        # s = "ab", k = 4, output: "ac"
        # s = "ad", k = 4, output: "ba"

        # TC: O(n), SC: O(n)
        s = list(s)
        i = len(s) - 1
        s[i] = chr(ord(s[i]) + 1)   # Increment the last letter
        # Loop over char from right to left, until either i == -1 or i == len(num)
        while 0 <= i < len(s):
            # If current elem >= k, should reset this elem to be 'a', decrement i, so we can increment the left element
            if ord(s[i]) - ord('a') >= k:
                s[i] = 'a'
                i -= 1
                s[i] = chr(ord(s[i]) + 1)
            # If we have palindrome, blindly increment the current char, the code will adjust it
            elif (i >= 1 and s[i] == s[i-1]) or (i >= 2 and s[i] == s[i-2]):
                s[i] = chr(ord(s[i])+1)
            else:
                i += 1
        
        return '' if i < 0 else ''.join(s)

Time Complexity: $O(n)$, n is the length of s, since we only traverse from right to left.
Space Complexity: $O(n)$