Lexicographically Smallest Beautiful String
HardPrompt
A string is beautiful if:
- It consists of the first
kletters of the English lowercase alphabet. - It does not contain any substring of length
2or 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, anddis greater thanc.
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 <= 1054 <= k <= 26sis a beautiful string.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach involves generating every possible string that is lexicographically larger than the input string s, one by one. For each generated string, we check if it meets the criteria of a "beautiful" string. The first one that satisfies the conditions is our answer.
Algorithm
- Start with the input string
s. - Enter a loop that generates the next lexicographically larger string, let's call it
current_s. - To generate
current_sfroms:- Convert
sto a character arraychars. - Iterate from
i = n-1down to0. - Increment
chars[i]. - If
chars[i]is less than'a' + k, we have found the next string. Break the inner loop. - If
chars[i]becomes equal to'a' + k, setchars[i] = 'a'and continue to the next position to the left (this is a carry-over operation). - If the inner loop finishes (i.e., we carried over from index 0), it means we have exhausted all strings of length
n. There is no solution.
- Convert
- Check if
current_sis beautiful:- Iterate from
i = 0ton-1. - Check if
chars[i] == chars[i-1](fori > 0). - Check if
chars[i] == chars[i-2](fori > 1). - If any check fails, the string is not beautiful. Go back to the beginning of the main loop to generate the next string.
- Iterate from
- If
current_sis beautiful, convertcharsto a string and return it. - If the generation process exhausts all possibilities without finding a solution, return an empty string.
Walkthrough
The core idea is to treat the strings as numbers in base k, where 'a' corresponds to 0, 'b' to 1, and so on. We start with the string s and repeatedly find the "next" string in lexicographical order. The process of finding the next string is analogous to adding one to a number. We start from the rightmost character and increment it. If the character exceeds the allowed limit ('a' + k - 1), we reset it to 'a' and "carry over" the increment to the character on its left.
After generating a new string, we must validate if it's "beautiful". A string is beautiful if it only contains the first k letters and has no palindromic substrings of length 2 or 3. This means for any index i, s[i] != s[i-1] and s[i] != s[i-2]. This validation check takes linear time, O(n).
We continue this process of generating and validating until we find a beautiful string or exhaust all possible strings of length n that are larger than s.
class Solution { public String smallestBeautifulString(String s, int k) { char[] chars = s.toCharArray(); int n = s.length(); while (true) { // Increment the string like a base-k number int i = n - 1; while (i >= 0) { chars[i]++; if (chars[i] < 'a' + k) { break; } chars[i] = 'a'; i--; } // If i < 0, we have overflowed, no more strings if (i < 0) { return ""; } // Check if the new string is beautiful if (isBeautiful(chars)) { // We need to construct the rest of the string to be minimal // This simple brute force doesn't do that, it just checks the next permutation. // A better brute force would fill the rest with 'a's and check. // But the core issue of iterating one by one remains. // For the sake of demonstrating the concept, let's assume a full beautiful check. return new String(chars); } } } private boolean isBeautiful(char[] chars) { for (int i = 0; i < chars.length; i++) { if (i > 0 && chars[i] == chars[i-1]) { return false; } if (i > 1 && chars[i] == chars[i-2]) { return false; } } return true; }}Note: The provided code is a conceptual illustration. A direct implementation of generating every single next string and checking it would be too slow. The main flaw is the sheer number of candidates to check.
Complexity
Time
O(M * n), where `M` is the number of strings between `s` and the result. In the worst case, `M` can be very large (e.g., on the order of `k^n`), making this approach infeasible for the given constraints.
Space
O(n) to store the character array for the current string.
Trade-offs
Pros
Conceptually simple and easy to understand.
Cons
Extremely inefficient. It will time out for the given constraints (
nup to 10^5) because the number of strings to check can be astronomically large.Performs a lot of redundant work by re-validating the entire string from scratch for every single increment.
This is an efficient, greedy approach. To find the lexicographically smallest string larger than s, we should make the smallest possible change, and as far to the right as possible. We iterate from the right end of the string, trying to increment the character at each position. Once we successfully increment a character while keeping it "beautiful" with respect to its predecessors, we fill the rest of the string to its right with the smallest possible beautiful characters.
Algorithm
- Convert the input string
sto a character arraycharsfor efficient modification. - Iterate
ifrom the end of the string (n-1) down to the beginning (0). - For the character
chars[i], try to find a valid replacementc. Start checking fromc = chars[i] + 1. - Loop
cfromchars[i] + 1up to'a' + k - 1. - Check if
cis valid at positioni. A character is valid if it's not equal to the two preceding characters:cmust not be equal tochars[i-1](ifi > 0).cmust not be equal tochars[i-2](ifi > 1).
- If a valid
cis found:- This position
iis our "pivot". Updatechars[i] = c. - Now, fill the suffix of the string from
j = i + 1ton-1. - For each position
j, greedily find the smallest characterfill_c(starting from 'a') that is valid (i.e., not equal tochars[j-1]orchars[j-2]). - Update
chars[j] = fill_c. - After the suffix is filled, convert
charsback to a string and return it. This is the final answer.
- This position
- If the outer loop (from
n-1to0) completes without finding a valid replacement for any character, it means no such string exists. Return an empty string.
Walkthrough
The algorithm starts by scanning the string s from right to left (from index n-1 down to 0). At each position i, we try to find a character c that is greater than s[i] but still within the first k letters.
For each potential character c, we must check if it's valid. A character is valid if it doesn't form a palindrome with the characters at i-1 and i-2. That is, c must not be equal to s[i-1] or s[i-2].
If we find such a valid character c, we have found our "pivot". We update the character at index i to c. Then, we must fill all the subsequent positions (j > i) to make the resulting string as small as possible lexicographically. For each position j from i+1 to n-1, we greedily pick the smallest possible character ('a', 'b', 'c', ...) that is valid (i.e., doesn't equal the characters at j-1 and j-2). Since the problem guarantees k >= 4, a valid character among 'a', 'b', 'c' is always guaranteed to exist.
Once we have modified the character at i and filled the rest of the string, we have found our answer. If we iterate through all positions and cannot find any character to increment, no such string exists.
class Solution { public String smallestBeautifulString(String s, int k) { char[] chars = s.toCharArray(); int n = chars.length; // Iterate from right to left for (int i = n - 1; i >= 0; i--) { // Try to increment the character at position i for (char c = (char)(chars[i] + 1); c < 'a' + k; c++) { // Check if the new character c is valid (no length-2 or -3 palindrome) if ((i > 0 && c == chars[i - 1]) || (i > 1 && c == chars[i - 2])) { continue; // Invalid, try next character } // Found a valid character, this is our pivot chars[i] = c; // Fill the rest of the string from i + 1 to n - 1 for (int j = i + 1; j < n; j++) { // Find the smallest valid character for position j for (char fillChar = 'a'; fillChar < 'a' + k; fillChar++) { if ((j > 0 && fillChar == chars[j - 1]) || (j > 1 && fillChar == chars[j - 2])) { continue; } chars[j] = fillChar; break; // Found the smallest, move to next position } } return new String(chars); } } // If we went through the whole loop, no such string exists return ""; }}Complexity
Time
O(n * k). The outer loop runs at most `n` times. For each position, we might try up to `k` characters. Once a pivot is found at index `p`, filling the `n-p-1` suffix takes `O(n-p)` time, as each character fill is constant time (due to `k>=4`). The total time is dominated by finding the pivot, which in the worst case (pivot at index 0) is `O(n*k)`. Since `k` is a small constant (<= 26), this is effectively a linear time complexity, `O(n)`.
Space
O(n) to store the character array. If modification of the input string is allowed, space can be considered O(1) (excluding the space for the output string).
Trade-offs
Pros
Highly efficient and guaranteed to find the optimal solution.
The time complexity is effectively linear with respect to the length of the string, making it suitable for large inputs.
Correctly leverages the problem constraints (
k >= 4) to ensure an efficient solution.
Cons
The logic is slightly more complex to implement compared to a naive brute-force approach.
Solutions
Solution
class Solution {public String smallestBeautifulString(String s, int k) { int n = s.length(); char[] cs = s.toCharArray(); for (int i = n - 1; i >= 0; --i) { int p = cs[i] - 'a' + 1; for (int j = p; j < k; ++j) { char c = (char)('a' + j); if ((i > 0 && cs[i - 1] == c) || (i > 1 && cs[i - 2] == c)) { continue; } cs[i] = c; for (int l = i + 1; l < n; ++l) { for (int m = 0; m < k; ++m) { c = (char)('a' + m); if ((l > 0 && cs[l - 1] == c) || (l > 1 && cs[l - 2] == c)) { continue; } cs[l] = c; break; } } return String.valueOf(cs); } } return ""; }}class Solution {public: string smallestBeautifulString(string s, int k) { int n = s.size(); for (int i = n - 1; i >= 0; --i) { int p = s[i] - 'a' + 1; for (int j = p; j < k; ++j) { char c = (char)('a' + j); if ((i > 0 && s[i - 1] == c) || (i > 1 && s[i - 2] == c)) { continue; } s[i] = c; for (int l = i + 1; l < n; ++l) { for (int m = 0; m < k; ++m) { c = (char)('a' + m); if ((l > 0 && s[l - 1] == c) || (l > 1 && s[l - 2] == c)) { continue; } s[l] = c; break; } } return s; } } return ""; }};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 ''Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.