Lexicographically Smallest Beautiful String — Solution
Lexicographically Smallest Beautiful String solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Lexicographically Smallest Beautiful String is a hard coding problem on strings and greedy, asked in Amazon and Google interviews.
- Difficulty: Hard
- Topics: Strings, Greedy
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A string is beautiful when:
- it uses only the first
klowercase letters of the alphabet, and - it contains no palindromic substring of length 2 or more.
You are given a beautiful string s of length n and the integer k. Return the lexicographically smallest beautiful string of length n that is strictly larger than s, or an empty string if there is none.
Example 1
Input: s = "kaib", k = 12
Output: "kaic"
Explanation: Raising the last letter to `c` keeps every window palindrome-free.
Example 2
Input: s = "dcb", k = 4
Output: ""
Explanation: With only `a`–`d`, no position can be raised without creating a palindrome.
Example 3
Input: s = "abcd", k = 4
Output: "abda"
Explanation: The last letter is already `d`; raise the third to `d` and fill the rest with the smallest safe letter.
Constraints
1 <= n == s.length <= 10^54 <= k <= 26s is a beautiful string
Hints for Lexicographically Smallest Beautiful String
Hint 1
A string has no palindromic substring of length >= 2 exactly when no character equals either of the two characters before it.
Hint 2
To get the next string, keep the longest possible prefix of
s: try to raise the last position first, then the one before it, and so on.Hint 3
At position
i, try letters aboves[i](belowk) that differ from the two previous letters. Once one works, fill every later position with the smallest letter that differs from its two predecessors — withk >= 4one ofa,b,calways works.
How to solve Lexicographically Smallest Beautiful String
Beauty is a local rule (each letter differs from the previous two), so the next beautiful string keeps the longest prefix of s it can, bumps one position minimally, and fills the tail greedily with the smallest legal letters.
Approach
- Convert
sto letter indicesa[0..n-1]. - For
ifromn - 1down to 0: look for the smallestcwitha[i] < c < k,c != a[i-1]andc != a[i-2](where those exist). - If found, set
a[i] = c, then for eachj > iseta[j]to the smallest letter different froma[j-1]anda[j-2], and return the result. - If no position can be raised, return the empty string.
Why it works
A palindrome of length >= 2 contains a palindrome of length 2 or 3 at its centre, so forbidding x[j] == x[j-1] and x[j] == x[j-2] is equivalent to beauty. The answer must share the longest possible prefix with s and then have a larger letter at the first difference, and that letter should be as small as possible; after it, any suffix is allowed, so the smallest choice letter by letter is optimal — and it always exists because at most two letters are forbidden while k >= 4.
Complexity
- Time —
O(n · k) - Space —
O(n)
Pitfalls
- Checking only adjacent letters misses length-3 palindromes like
aba. - The new letter must stay below
k, not belowz. - When filling the tail, check against the new letters already placed, not the original
s.
Reference solution
Python
def smallestBeautifulString(s: str, k: int) -> str:
a = [ord(c) - 97 for c in s]
n = len(a)
for i in range(n - 1, -1, -1):
c = a[i] + 1
while c < k and ((i >= 1 and a[i - 1] == c) or (i >= 2 and a[i - 2] == c)):
c += 1
if c < k:
a[i] = c
for j in range(i + 1, n):
x = 0
while (j >= 1 and a[j - 1] == x) or (j >= 2 and a[j - 2] == x):
x += 1
a[j] = x
return "".join(chr(97 + x) for x in a)
return ""Java
public static String smallestBeautifulString(String s, int k) {
int n = s.length();
char[] a = s.toCharArray();
for (int i = n - 1; i >= 0; i--) {
int c = a[i] - 'a' + 1;
while (c < k && ((i >= 1 && a[i - 1] - 'a' == c) || (i >= 2 && a[i - 2] - 'a' == c))) c++;
if (c < k) {
a[i] = (char) ('a' + c);
for (int j = i + 1; j < n; j++) {
int x = 0;
while ((j >= 1 && a[j - 1] - 'a' == x) || (j >= 2 && a[j - 2] - 'a' == x)) x++;
a[j] = (char) ('a' + x);
}
return new String(a);
}
}
return "";
}C++
string smallestBeautifulString(string s, int k) {
int n = s.size();
for (int i = n - 1; i >= 0; i--) {
int c = s[i] - 'a' + 1;
while (c < k && ((i >= 1 && s[i - 1] - 'a' == c) || (i >= 2 && s[i - 2] - 'a' == c))) c++;
if (c < k) {
s[i] = (char)('a' + c);
for (int j = i + 1; j < n; j++) {
int x = 0;
while ((j >= 1 && s[j - 1] - 'a' == x) || (j >= 2 && s[j - 2] - 'a' == x)) x++;
s[j] = (char)('a' + x);
}
return s;
}
}
return "";
}JavaScript
var smallestBeautifulString = function(s, k) {
var n = s.length;
var a = [];
for (var q = 0; q < n; q++) a.push(s.charCodeAt(q) - 97);
for (var i = n - 1; i >= 0; i--) {
var c = a[i] + 1;
while (c < k && ((i >= 1 && a[i - 1] === c) || (i >= 2 && a[i - 2] === c))) c++;
if (c < k) {
a[i] = c;
for (var j = i + 1; j < n; j++) {
var x = 0;
while ((j >= 1 && a[j - 1] === x) || (j >= 2 && a[j - 2] === x)) x++;
a[j] = x;
}
var res = "";
for (var p = 0; p < n; p++) res += String.fromCharCode(97 + a[p]);
return res;
}
}
return "";
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Greedy Algorithms