Skip to main content
Talentd

Lexicographically Smallest Beautiful String - Solution & Explanation

HardStringGreedy16 min readAsked at: Amazon, Google
Practice this problem

Problem Statement

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

Approach Overview

Problem Overview: You are given a string s and an integer k representing the first k lowercase letters ('a' to 'a' + k - 1). A string is beautiful if no character equals the previous one or the one two positions before it. The task is to find the lexicographically smallest beautiful string strictly greater than s.

Approach 1: Backtrack and Increment (O(n * k) time, O(1) space)

This method treats the string like a base-k number and increments it from right to left. Start from the last position and try increasing the current character. After each increment, check whether it violates the beauty rule (s[i] != s[i-1] and s[i] != s[i-2]). If the character is valid, rebuild the suffix greedily with the smallest valid characters that keep the string beautiful. If no valid increment exists at a position, move left and continue backtracking.

The key insight: once you increase a character at position i, the prefix becomes fixed. The suffix can then be rebuilt with the smallest valid characters to maintain lexicographic minimality. This approach simulates controlled backtracking while preserving the lexicographically smallest valid continuation. It relies heavily on simple character checks and sequential iteration, making it efficient for constraints typically seen in string problems.

Approach 2: Greedy Character Replacement (O(n * k) time, O(1) space)

The greedy strategy scans the string from right to left and attempts to replace each character with the next valid option. For index i, iterate characters from s[i] + 1 to 'a' + k - 1. Choose the first character that doesn't match the previous two characters. Once a valid replacement is found, rebuild the remaining suffix by picking the smallest valid character at each step.

This works because lexicographic order is determined by the earliest differing character. Increasing the rightmost possible index ensures the smallest overall increase. The suffix reconstruction step uses a greedy rule: always choose the smallest character that doesn't conflict with the previous two positions. The approach combines simple iteration with constraints typical in greedy algorithms and local validation rules from string manipulation.

Recommended for interviews: The greedy right-to-left increment approach is what most interviewers expect. It demonstrates understanding of lexicographic ordering, constraint validation, and suffix reconstruction. Mentioning the backtracking interpretation shows deeper reasoning, but implementing the greedy increment + rebuild pattern proves strong problem‑solving skills.

Approach 1: Backtrack and Increment Approach

This approach involves starting from the end of the string and incrementing characters lexicographically. If a valid increment is found, backtrack over the string to ensure no palindromic substrings are formed.

This Python function iterates through the string from right to left, attempting to increment each character while checking if the resultant string remains beautiful. If a valid increment is found at any position, subsequent characters are filled with the smallest lexicographical values permissible to maintain the beauty of the string.

Code

PythonJava

Python

Java

Complexity

Time Complexity: O(n*k)
Space Complexity: O(n)

Try this approach in the editor →

Approach 2: Greedy Character Replacement

The greedy approach builds the new string from the start, replacing each character with the smallest possible character larger than itself wherever necessary to ensure beauty. If incrementing from a certain point doesn't work, it tries the next character.

This C++ code iterates through the string from the end and tries to replace each character with the next possible lexicographical character, ensuring that it remains a beautiful string by checking against palindromic substrings at each step. Upon success, it greedily fills subsequent characters with the smallest valid characters.

Code

C++JavaScript

C++

JavaScript

Complexity

Time Complexity: O(n*k)
Space Complexity: O(n)

Try this approach in the editor →

Approach 3: 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.

We can greedily search backwards from the last index of the string, find an index i such that the character at index i can be replaced by a slightly larger character, while ensuring that it is different from its two previous adjacent characters.

  • If such an index i is found, then we replace s[i] with c, and replace the characters from s[i+1] to s[n-1] with the characters in the first k characters of the alphabet in the order of the minimum dictionary that are not the same as the previous two adjacent characters. After the replacement is completed, we obtain a beautiful string that is the smallest in the dictionary and greater than s.
  • If such an index i cannot be found, then we cannot construct a beautiful string greater than s in dictionary order, so return an empty string.

The time complexity is O(n), where n is the length of the string. The space complexity is O(1).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Backtrack and Increment Approach

Time Complexity: O(n*k)
Space Complexity: O(n)

Greedy Character Replacement

Time Complexity: O(n*k)
Space Complexity: O(n)

Greedy—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Backtrack and IncrementO(n * k)O(1)Useful for understanding the search space and how lexicographic increments propagate when constraints break.
Greedy Character ReplacementO(n * k)O(1)Preferred solution in interviews. Efficiently finds the next valid string by incrementing from the right and rebuilding the suffix.

Video Solution

Leetcode Weekly contest 343 - Hard - Lexicographically Smallest Beautiful String • Prakhar Agrawal • 1,358 views views

Watch 5 more video solutions →

Frequently Asked Questions

Is Lexicographically Smallest Beautiful String easy or hard?
LeetCode classifies this problem as Hard because it combines lexicographic ordering with strict local constraints. The tricky part is ensuring that after incrementing a character, the remaining suffix is rebuilt in the smallest valid way while preserving the beauty rule.
Lexicographically Smallest Beautiful String Python/Java solution
Implement the algorithm by converting the string to a mutable character array. Traverse from right to left, attempt to increment the current character, and check the beauty constraints. After a valid replacement, rebuild the suffix using the smallest possible characters. The same logic works in Python, Java, C++, and JavaScript.
How to solve Lexicographically Smallest Beautiful String in O(n)?
A near linear scan is achieved by iterating from right to left and performing constant validation checks for each candidate character. Although up to k characters may be tested per position, k is usually small (limited alphabet size). After finding a valid increment, rebuild the suffix greedily to maintain the beauty constraint.
What is the best approach for Lexicographically Smallest Beautiful String?
The greedy right-to-left increment approach is the most effective solution. Start from the last index, try increasing the character, and ensure it doesn't match the previous two characters. Once a valid character is placed, rebuild the remaining suffix with the smallest valid characters. This guarantees the lexicographically smallest beautiful string greater than the input.
Is Lexicographically Smallest Beautiful String asked at Google/Amazon/Meta?
Variants of lexicographic string construction and constraint-based string generation appear in interviews at companies like Google, Amazon, and Meta. These problems test greedy reasoning, constraint validation, and careful string manipulation under ordering rules.
What data structure is used in Lexicographically Smallest Beautiful String?
The solution primarily uses basic string or character array manipulation. No complex data structures are required. The algorithm relies on sequential iteration, lexicographic comparison, and simple constraint checks against the previous two characters.
What is the time complexity of Lexicographically Smallest Beautiful String?
The time complexity is O(n * k), where n is the string length and k is the number of allowed characters. For each position, the algorithm may try up to k characters and perform constant checks against the previous two positions. Space complexity remains O(1) since the string is modified in place.

Ready to solve this problem?

Practice Lexicographically Smallest Beautiful String with our built-in code editor and test cases.

Practice on FleetCode
Previous

Find Palindrome With Fixed Length

Next

Smallest String With Swaps