2663. Lexicographically Smallest Beautiful String

HardGreedyString

Problem Description

In this problem, we are dealing with the concept of beautiful strings. A string is considered beautiful if two conditions are met:

It is composed only of the first k letters of the English lowercase alphabet.
It does not contain any palindromic substring of length 2 or more.

Given a beautiful string s with a length of n and a positive integer k, the task is to find the next lexicographically smallest beautiful string that is larger than s. The lexicographic order is like dictionary order - for example, b is larger than a, ab is larger than aa, and so on. If the string contains a letter at some position where it differs from another string and this letter is bigger, the entire string is considered larger in lexicographic order.

To solve the problem, we want to:

Preserve the "beautiful" characteristic of the string.
Increment the string in the minimal way to find the next lexicographically larger string.

Intuition

The intuitive approach to this problem is to use a greedy strategy. The goal is to find the smallest lexicographical increment possible that results in a string fulfilling the beauty criteria.

Take the following steps:

Start from the end of the given string s and move backwards to find the first place where we can increment a character without breaking the beauty rules.
Once such a place is found, replace the character at that position with the next possible character that does not create a palindrome with the two previous characters.
After replacing a character, it is necessary to build the rest of the string from that point onward with the smallest possible characters from the set of allowed first k characters also while avoiding the creation of palindromic substrings.
If no such position exists, then it is not possible to create a lexicographically larger beautiful string, and an empty string should be returned as per the problem statement.

This greedy approach ensures that the resulting string is strictly the next lexicographically larger string since only the necessary changes are made starting from the back, and each replacement ensures the smallest viable increment.

Learn more about Greedy patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What's the output of running the following function using the following tree as input?

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12

1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18

1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

1 2 3 6 x x1 2 3 x x x 6 x x1 2 6 x x x 3 x x

I don’t know

Solution Approach

The provided reference solution uses a backwards greedy algorithm to build the lexicographically smallest beautiful string that comes after the given string s. Here's the step-by-step approach based on the code:

We initialize a variable n with the length of the given string s and convert the string to a list of characters, cs.
The algorithm then iterates over cs from the last character to the first. For each character, it tries to find the next character in the alphabet that can be placed at that position to make the string lexicographically larger while maintaining the non-palindrome property.

To do this, it converts the character to its numerical equivalent (p = ord(cs[i]) - ord('a') + 1) and iterates from p to k-1 to find a suitable replacement.
A replacement is deemed suitable if it isn't the same as the character immediately before it (cs[i - 1]) or the one two positions before (cs[i - 2]). This ensures that substrings of length 2 or 3 are not palindromic.
Once a suitable character is found for position i, the code updates cs[i] and moves on to filling the rest of the string from i + 1 to n - 1. For this remaining part, the smallest possible character that does not form a palindrome with the previous two characters is selected. Again, this is checked by comparing against the characters at positions l - 1 and l - 2.
When the loop successfully updates the character array cs, the newly formed string is returned by joining the list of characters.
If the loop terminates without finding a suitable replacement for any of the positions, it means no lexicographically larger beautiful string can be formed, and therefore an empty string '' is returned.

The above algorithm effectively uses a linear scan of the input string in the worst-case scenario, making the time complexity linear in relation to the length of s. The use of a fixed-size ASCII offset (ord('a')) ensures a constant time operation for character to integer conversion, providing an efficient means to compare and assign characters.

In summary, the approach relies on a greedy algorithm that backs up from the end of the string to find the smallest necessary increments while maintaining the string's beauty, taking advantage of character-integer conversions and simple comparisons to enforce the beauty constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which two pointer technique does Quick Sort use?

Fast-slow pointersTwo pointers moving in opposite directionSliding windowPrefix sum

I don’t know

Example Walkthrough

Let's take a small example to illustrate the solution approach. Imagine we have a beautiful string s = "abac" and k = 3 (meaning we can only use the first 3 letters of the English alphabet: a, b, c).

Following the solution approach, we perform the following steps:

Start from the end of s, which is the character c. We need to find a place where we can increment a character without creating palindrome substrings.
The last character c is already the maximum for k = 3, so we move backward. Before c, there is an a, but increasing a to b would form bb, which is a palindrome. Therefore, we continue moving backward.
Before a, we have b. We can't increment b to c because that will create the palindrome cac.
We reach the first character a. We can increment a to b resulting in the string bbac. However, this forms a palindrome bb. Hence, we have to increment b to c, ensuring no direct repetition with its neighboring character.
Now we have cbac, but we are not allowed to have direct repetitions or create palindromic substrings such as cac. Since c is already the maximum allowed character for our k, we must convert the subsequential characters to the smallest possible characters (a), ensuring that we do not form a palindrome. However, placing a after c would give us caa, which is a palindrome; thus we must place a b instead.
Following this pattern, the next characters will be the lowest possible values ensuring no palindromic substrings are created. After b, the smallest allowed character which doesn't create a palindrome is a.
The resulting string is cbab which is the smallest lexicographic increment from our original string abac that keeps the string beautiful.

So, the solution algorithm would output cbab as the next lexicographically smallest beautiful string after abac when using the first 3 lowercase letters of the alphabet.

Solution Implementation

1class Solution:
2    def smallestBeautifulString(self, s: str, k: int) -> str:
3        # Get the length of the string
4        string_length = len(s)
5
6        # Convert the string to a list for easier manipulation
7        char_list = list(s)
8
9        # Iterate backwards through the character list
10        for i in range(string_length - 1, -1, -1):
11            # Find the position of the current character in the alphabet (1-based)
12            position = ord(char_list[i]) - ord('a') + 1
13
14            # Try replacing current character with the next possible beautiful character
15            for replacement_pos in range(position, k):
16                # Calculate the replacement character based on its position
17                replacement_char = chr(ord('a') + replacement_pos)
18
19                # Check if the previous two characters are the same as the potential replacement character
20                # If so, skip this replacement
21                if (i > 0 and char_list[i - 1] == replacement_char) or (i > 1 and char_list[i - 2] == replacement_char):
22                    continue
23
24                # Assign the replacement character to the current position
25                char_list[i] = replacement_char
26
27                # For remainder of the string, place lexicographically smallest possible character
28                for l in range(i + 1, string_length):
29                    # Iterate over possible characters
30                    for m in range(k):
31                        next_char = chr(ord('a') + m)
32                        # Skip if the character matches any of the previous two characters
33                        if (l > 0 and char_list[l - 1] == next_char) or (l > 1 and char_list[l - 2] == next_char):
34                            continue
35                        # Assign and break since the smallest possible character has been found
36                        char_list[l] = next_char
37                        break
38              
39                # Return the modified string after the first replacement
40                return ''.join(char_list)
41
42        # Return an empty string if no possibility to make the string beautiful
43        return ''
44

1class Solution {
2    public String smallestBeautifulString(String s, int k) {
3        // Length of the input string
4        int n = s.length();
5        // Convert the input string to a character array for manipulation
6        char[] chars = s.toCharArray();
7      
8        // Iterating from the end of the character array
9        for (int i = n - 1; i >= 0; --i) {
10            // Calculate the numeric position of the current character
11            int position = chars[i] - 'a' + 1;
12            // Iterate through the alphabet starting from the character after the current one
13            for (int j = position; j < k; ++j) {
14                // Convert the numeric position into a character
15                char nextChar = (char) ('a' + j);
16                // Check if replacing the current character with the next one obeys the rules 
17                // (next character should not be the same as the previous two characters)
18                if ((i > 0 && chars[i - 1] == nextChar) || (i > 1 && chars[i - 2] == nextChar)) {
19                    continue;
20                }
21                // Assign the new character to the current position
22                chars[i] = nextChar;
23                // Iterate over the remaining characters in the array starting from i+1
24                for (int l = i + 1; l < n; ++l) {
25                    // Iterate over all possible characters within the given limit 'k'
26                    for (int m = 0; m < k; ++m) {
27                        nextChar = (char) ('a' + m);
28                        // Apply the same rule for the next characters
29                        if ((l > 0 && chars[l - 1] == nextChar) || (l > 1 && chars[l - 2] == nextChar)) {
30                            continue;
31                        }
32                        // Assign the chosen character and break to the next position
33                        chars[l] = nextChar;
34                        break;
35                    }
36                }
37                // Return the new string after constructing it from the character array
38                return String.valueOf(chars);
39            }
40        }
41        // If no valid string can be formed, return an empty string
42        return "";
43    }
44}
45

1class Solution {
2public:
3    // Function to create the smallest lexicographically string that follows specific rules
4    string smallestBeautifulString(string s, int k) {
5        int n = s.size(); // Get the length of the input string
6      
7        // Iterate backward through the string
8        for (int i = n - 1; i >= 0; --i) {
9            int position = s[i] - 'a' + 1; // Convert character to zero-based position
10          
11            // Try each possible character starting from the current position to k - 1
12            for (int j = position; j < k; ++j) {
13                char c = 'a' + j; // Convert integer position j to its corresponding character
14              
15                // Skip characters that are illegal due to the rules (same as previous one or two)
16                if ((i > 0 && s[i - 1] == c) || (i > 1 && s[i - 2] == c)) {
17                    continue;
18                }
19              
20                s[i] = c; // Set the current character of the string s
21              
22                // Update the rest of the string after the current position
23                for (int l = i + 1; l < n; ++l) {
24                    // Try each character from 'a' to 'a' + (k - 1)
25                    for (int m = 0; m < k; ++m) {
26                        c = 'a' + m;
27                      
28                        // Apply the same rules, skip if the character is illegal
29                        if ((l > 0 && s[l - 1] == c) || (l > 1 && s[l - 2] == c)) {
30                            continue;
31                        }
32                      
33                        // Set the next character in the string s
34                        s[l] = c;
35                        break; // Break to fill the next position in the string
36                    }
37                }
38              
39                return s; // Return the updated string once it is built
40            }
41        }
42      
43        return ""; // Return an empty string if no valid string can be formed
44    }
45};
46

1function smallestBeautifulString(inputString: string, alphabetSize: number): string {
2    // Split the input string into an array of characters
3    const characters: string[] = inputString.split('');
4    // Get the length of the character array
5    const length = characters.length;
6
7    // Loop backwards through the characters
8    for (let index = length - 1; index >= 0; --index) {
9        // Calculate the alphabet position of the current character and increment it by 1 (to find next character)
10        const currentCharPos = characters[index].charCodeAt(0) - 'a'.charCodeAt(0) + 1;
11      
12        // Loop over the possible characters (starting from currentCharPos to alphabetSize)
13        for (let charCode = currentCharPos; charCode < alphabetSize; ++charCode) {
14            // Get the character representation of charCode
15            let nextChar = String.fromCharCode(charCode + 'a'.charCodeAt(0));
16          
17            // Check the adjacent characters to avoid consecutive duplicates
18            if ((index > 0 && characters[index - 1] === nextChar) ||
19                (index > 1 && characters[index - 2] === nextChar)) {
20                continue;
21            }
22          
23            // Update the current character in the array
24            characters[index] = nextChar;
25          
26            // Fill the rest of the string with non-repeating characters
27            for (let nextIndex = index + 1; nextIndex < length; ++nextIndex) {
28                // Try characters from 'a' to the kth letter in the alphabet
29                for (let nextCharCode = 0; nextCharCode < alphabetSize; ++nextCharCode) {
30                    nextChar = String.fromCharCode(nextCharCode + 'a'.charCodeAt(0));
31                  
32                    // Check the adjacent characters to avoid consecutive duplicates
33                    if ((nextIndex > 0 && characters[nextIndex - 1] === nextChar) ||
34                        (nextIndex > 1 && characters[nextIndex - 2] === nextChar)) {
35                        continue;
36                    }
37                  
38                    // Update the character at nextIndex with the non-repeating character
39                    characters[nextIndex] = nextChar;
40                    break;
41                }
42            }
43          
44            // Convert the array back to a string and return the resultant string
45            return characters.join('');
46        }
47    }
48  
49    // If no beautiful string could be formed, return an empty string
50    return '';
51}
52

Not Sure What to Study? Take the 2-min Quiz：

What are the most two important steps in writing a depth first search function? (Select 2)

Determine state to pass down to recursive function callDetermine return valueDetermine how many recursive calls will be madeTracing the recursive calls

Time and Space Complexity

Time Complexity

The time complexity of the code is actually not O(n). In the worst case, both of the nested loops could iterate up to k times for each position. The outer loop runs from n-1 down to 0, contributing an O(n) factor. Inside this loop, we have the second loop iterating through the possible characters less than k, giving a factor of O(k). Similarly, the innermost loop, which resets each character after the current position, iterates up to k times for each remaining position, leading to a factor of O(k * (n - i)). Therefore, the worst-case time complexity is closer to O(n * k^2).

Space Complexity

The space complexity is indeed O(1), assuming that the space needed for the input string s is not counted as additional space since we're transforming it in-place into a list cs. The only additional space used is for a few variables to store indices and characters, which does not scale with the input size, hence constant space complexity.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

How would you design a stack which has a function min that returns the minimum element in the stack, in addition to push and pop? All push, pop, min should have running time O(1).

Add another stack to store the minimumsAdd a heap to store the minimumsAdd a variable to track the minimumAdd a queue to store the minumums

I don’t know

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

2663. Lexicographically Smallest Beautiful String

Problem Description

Intuition

Solution Approach

Example Walkthrough

Solution Implementation

Time and Space Complexity

Time Complexity

Space Complexity

Recommended Readings