LeetCode 2663 - Lexicographically Smallest Beautiful String

The problem requires generating the lexicographically smallest beautiful string that is strictly larger than a given beautiful string s. A string is beautiful if it uses only the first k letters of the English alphabet and contains no palindromic substring of length 2 or more.

leetcodehardstringgreedy

LeetCode Problem 2663

Difficulty: 🔴 Hard
Topics: String, Greedy

Solution

Problem Understanding

The problem requires generating the lexicographically smallest beautiful string that is strictly larger than a given beautiful string s. A string is beautiful if it uses only the first k letters of the English alphabet and contains no palindromic substring of length 2 or more. Essentially, no two consecutive letters can be the same, and no three consecutive letters can form a palindrome.

The input consists of a string s of length n and an integer k specifying the allowable alphabet. The output must be the smallest string that is strictly lexicographically larger than s and still adheres to the beautiful string constraints. If no such string exists, an empty string should be returned.

The constraints imply that n can be as large as 100,000, so any naive approach that generates all possible strings will be infeasible. Since k is at least 4, we are guaranteed enough letters to avoid creating a palindromic substring in almost all cases except when nearing the lexicographical maximum.

Important edge cases include when s is already the lexicographically largest beautiful string, or when small values of k limit the possible next characters, making it impossible to construct a valid string.

Approaches

Brute Force

A brute-force approach would attempt to increment s one character at a time, checking each candidate string to see if it is beautiful. For each position in the string, we would try all letters greater than the current one and recursively validate the rest. This guarantees correctness but is infeasible because it requires exploring an exponential number of strings for large n (up to k^n possibilities), which is computationally impossible for n = 10^5.

Optimal Approach

The key insight is greedy character replacement from the end. We try to increment the last character of s to the next lexicographically larger character. If that character forms a palindrome of length 2 or 3 with its preceding characters, we skip it and try the next possible character. Once a valid replacement is found, we fill the remaining positions with the smallest lexicographically valid characters to ensure minimality. If no valid character can be placed at a position, we backtrack to the previous position and try the next character there. This approach leverages the greedy choice property and ensures linear time complexity relative to n because each position is considered at most k times.

Approach Time Complexity Space Complexity Notes
Brute Force O(k^n) O(n) Generates all possible strings larger than s and checks beauty. Not feasible for large n.
Optimal O(n*k) O(n) Greedy increment from the end with local palindrome checks, filling minimal characters forward.

Algorithm Walkthrough

  1. Start from the last character of the string s and attempt to increment it to the next lexicographically larger character.
  2. For each candidate character, check if it violates the palindrome constraint with the previous one or two characters.
  3. If a valid character is found, place it and proceed to fill the subsequent positions with the smallest possible characters that maintain the beautiful string property.
  4. If no valid character can be placed at the current position, move one position to the left and repeat the process.
  5. Continue until either a valid string is formed or the first position has been exhausted. If no solution is possible, return an empty string.

Why it works: The algorithm maintains the invariant that all characters before the current index are fixed and valid. By greedily choosing the next lexicographically larger character at the first available position from the right and filling the rest minimally, we ensure the resulting string is both beautiful and the smallest possible string that is greater than s.

Python Solution

class Solution:
    def smallestBeautifulString(self, s: str, k: int) -> str:
        n = len(s)
        s = list(s)
        
        for i in range(n - 1, -1, -1):
            for c in range(ord(s[i]) + 1, ord('a') + k):
                char = chr(c)
                if (i >= 1 and s[i-1] == char) or (i >= 2 and s[i-2] == char):
                    continue
                s[i] = char
                for j in range(i + 1, n):
                    for next_c in range(ord('a'), ord('a') + k):
                        next_char = chr(next_c)
                        if (j >= 1 and s[j-1] == next_char) or (j >= 2 and s[j-2] == next_char):
                            continue
                        s[j] = next_char
                        break
                return "".join(s)
        return ""

The Python solution iterates from the end of the string, incrementing characters and checking for palindrome constraints. Once a valid increment is made, it greedily fills the rest of the string with the smallest allowable characters.

Go Solution

func smallestBeautifulString(s string, k int) string {
    n := len(s)
    arr := []byte(s)

    for i := n - 1; i >= 0; i-- {
        for c := arr[i] + 1; c < byte('a'+k); c++ {
            if (i >= 1 && arr[i-1] == c) || (i >= 2 && arr[i-2] == c) {
                continue
            }
            arr[i] = c
            for j := i + 1; j < n; j++ {
                for next := byte('a'); next < byte('a'+k); next++ {
                    if (j >= 1 && arr[j-1] == next) || (j >= 2 && arr[j-2] == next) {
                        continue
                    }
                    arr[j] = next
                    break
                }
            }
            return string(arr)
        }
    }
    return ""
}

In Go, the implementation uses a byte array for in-place modification of the string. The logic mirrors Python, using ASCII values for character manipulation and local palindrome checks.

Worked Examples

Example 1: s = "abcz", k = 26

Step i Candidate Palindrome check Action
Start 3 'd' Valid Place 'd'
Fill 4 'a' Valid Place 'a'
Result - - - "abda"

Example 2: s = "dc", k = 4

Step i Candidate Palindrome check Action
1 1 None N/A Backtrack
0 0 None N/A No valid options
Result - - - ""

Complexity Analysis

Measure Complexity Explanation
Time O(n*k) Each character is considered at most k times during increment and fill operations.
Space O(n) The string is converted to a mutable array to perform in-place modifications.

The algorithm is efficient for the given constraints because k is bounded by 26, and n can be up to 10^5, making O(n*k) feasible.

Test Cases

# Provided examples
assert Solution().smallestBeautifulString("abcz", 26) == "abda"  # Lexicographically next beautiful
assert Solution().smallestBeautifulString("dc", 4) == ""         # No valid next string

# Edge cases
assert Solution().smallestBeautifulString("a", 4) == "b"          # Single character increment
assert Solution().smallestBeautifulString("abcd", 4) == "abca"   # Filling minimal valid characters
assert Solution().smallestBeautifulString("zz", 26) == ""         # Already maximal string
assert Solution().smallestBeautifulString("abdc", 4) == "abda"   # Middle character change
Test Why
"abcz", 26 Standard case, next beautiful string exists
"dc", 4 No valid next string exists
"a", 4 Single character minimal case
"abcd", 4 Filling remaining positions to maintain minimality
"zz", 26 Already at lexicographic maximum
"abdc", 4 Requires incrementing a middle character

Edge Cases

  1. Single-character string: When n = 1, the algorithm must simply try the next character within bounds. The solution handles this by iterating from the last character, which is also the first.
  2. Maximal lexicographic string: When s consists of the largest k characters in sequence, no next string exists. The algorithm naturally backtracks to the first character and returns an empty string if no valid replacement is found.
  3. Small k values: For k = 4, there are fewer letters to choose from, so palindrome constraints can make it impossible to fill subsequent positions. The nested loops ensure that only valid characters are used and backtracking occurs when no valid character exists, preventing invalid strings.