#2663

Hard

auto_awesomeGreedy choice plus invariant validation

LeetCode Problem Workspace

Lexicographically Smallest Beautiful String

Find the lexicographically smallest beautiful string larger than the given string using greedy choice and invariant validation.

string greedy

Problem Statement

You are given a string s of length n composed of the first k lowercase letters. A string is considered beautiful if it contains no palindromic substrings of length 2 or 3. Your task is to find the lexicographically smallest beautiful string that is strictly larger than s.

If such a string exists, return it. Otherwise, return an empty string. Ensure that the resulting string respects the beauty rules for all substrings and uses only the first k letters. Input constraints guarantee s is already beautiful.

Examples

Example 1

Input: s = "abcz", k = 26

Output: "abda"

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: ""

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 <= 105
4 <= k <= 26
s is a beautiful string.

Solution Approach

Greedy Increment from Right

Start from the last character of s and try to increment it within the allowed k letters. Check each increment to ensure it does not create a palindrome of length 2 or 3. If a valid increment is found, fix the remaining positions with the smallest valid letters to maintain the beautiful property.

Invariant Validation for Palindromes

Maintain the invariant that no substring of length 2 or 3 is a palindrome. At each step, validate the chosen character against its previous two characters. This ensures that the partial string remains beautiful and prevents costly backtracking.

Early Termination and Result Construction

If no valid increment is possible at any position, move leftward until a feasible change is found. Once a valid change is applied, fill subsequent positions greedily with the smallest letters that preserve the invariant. Return the constructed string or empty string if no solution exists.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity is O(n*k) in the worst case due to trying up to k letters per position. Space complexity is O(n) to store the resulting string and temporary checks.

What Interviewers Usually Probe

They may ask how to efficiently check for palindromic substrings while modifying characters.
Expect questions about greedy approaches for lexicographical order with constraints.
They might probe the invariant maintenance and early termination strategy.

Common Pitfalls or Variants

Common pitfalls

Incrementing a character without checking the palindrome constraint leads to invalid strings.
Filling remaining characters without greedy choice can produce non-minimal lexicographical results.
Failing to handle the case where no valid larger string exists returns incorrect output.

Follow-up variants

Finding the lexicographically largest beautiful string smaller than a given string.
Generalizing to avoid palindromic substrings of length up to m instead of 2 and 3.
Allowing a custom alphabet instead of first k lowercase letters.

FAQ

What defines a beautiful string in this problem?

A beautiful string has no palindromic substrings of length 2 or 3 and uses only the first k lowercase letters.

Why is a greedy approach suitable here?

Greedy choice ensures each character is incremented minimally to maintain lexicographical order while validating the beauty invariant efficiently.

What if no lexicographically larger beautiful string exists?

Return an empty string as no solution can satisfy both the lexicographical and beauty constraints.

How do you verify the string remains beautiful?

Check the last two characters at each step to ensure no palindrome of length 2 or 3 is formed before fixing subsequent positions.

Can GhostInterview help identify failure points in this greedy approach?

Yes, it highlights where increments violate palindromic invariants and shows how to adjust subsequent characters to maintain beauty.

terminal

Solution

Solution 1: Greedy

We can find that a palindrome string of length $2$ must have two adjacent characters equal; and a palindrome string of length $3$ must have two characters at the beginning and end equal. Therefore, a beautiful string does not contain any palindrome substring of length $2$ or longer, which means that each character in the string is different from its previous two adjacent characters.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

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

Continue Practicing

#2645 minimum additions to make valid string #2697 lexicographically smallest palindrome #2712 minimum cost to make all characters equal