In this guide, you will get 2663. Lexicographically Smallest Beautiful String LeetCode Solution with the best time and space complexity. The solution to Lexicographically Smallest Beautiful String problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Lexicographically Smallest Beautiful String
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”.
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.
Complexity Analysis
Time Complexity:
Space Complexity:
2663. Lexicographically Smallest Beautiful String LeetCode Solution in C++
class Solution {
public:
string smallestBeautifulString(string s, int k) {
for (int i = s.length() - 1; i >= 0; --i) {
do {
++s[i];
} while (containsPalindrome(s, i));
if (s[i] < 'a' + k)
// If s[i] is among the first k letters, then change the letters after
// s[i] to the smallest ones that don't form any palindrome substring.
return changeSuffix(s, i + 1);
}
return "";
}
private:
// Returns true if s[0..i] contains any palindrome.
bool containsPalindrome(const string& s, int i) {
return (i > 0 && s[i] == s[i - 1]) || (i > 1 && s[i] == s[i - 2]);
}
// Returns a string, where replacing s[i..n) with the smallest possible
// letters don't form any palindrome substring.
string changeSuffix(string& s, int i) {
for (int j = i; j < s.length(); ++j)
for (s[j] = 'a'; containsPalindrome(s, j); ++s[j])
;
return s;
}
}; /* code provided by PROGIEZ */
2663. Lexicographically Smallest Beautiful String LeetCode Solution in Java
class Solution {
public String smallestBeautifulString(String s, int k) {
StringBuilder sb = new StringBuilder(s);
for (int i = s.length() - 1; i >= 0; --i) {
do {
sb.setCharAt(i, (char) (sb.charAt(i) + 1));
} while (containsPalindrome(sb, i));
if (sb.charAt(i) < 'a' + k)
// If sb[i] is among the first k letters, then change the letters after
// sb[i] to the smallest ones that don't form any palindrome substring.
return changeSuffix(sb, i + 1);
}
return "";
}
// Returns true if sb[0..i] contains any palindrome.
private boolean containsPalindrome(StringBuilder sb, int i) {
return (i > 0 && sb.charAt(i) == sb.charAt(i - 1)) ||
(i > 1 && sb.charAt(i) == sb.charAt(i - 2));
}
// Returns a string, where replacing sb[i..n) with the smallest possible
// letters don't form any palindrome substring.
private String changeSuffix(StringBuilder sb, int i) {
for (int j = i; j < sb.length(); ++j)
for (sb.setCharAt(j, 'a'); containsPalindrome(sb, j);
sb.setCharAt(j, (char) (sb.charAt(j) + 1)))
;
return sb.toString();
}
} // code provided by PROGIEZ
2663. Lexicographically Smallest Beautiful String LeetCode Solution in Python
class Solution:
def smallestBeautifulString(self, s: str, k: int) -> str:
chars = list(s)
for i in reversed(range(len(chars))):
chars[i] = chr(ord(chars[i]) + 1)
while self._containsPalindrome(chars, i):
chars[i] = chr(ord(chars[i]) + 1)
if chars[i] < chr(ord('a') + k):
# If s[i] is among the first k letters, then change the letters after
# s[i] to the smallest ones that don't form any palindrome substring.
return self._changeSuffix(chars, i + 1)
return ''
def _containsPalindrome(self, chars: list[str], i: int) -> bool:
"""Returns True if chars[0..i] contains palindrome."""
return ((i > 0 and chars[i] == chars[i - 1]) or
(i > 1 and chars[i] == chars[i - 2]))
def _changeSuffix(self, chars: list[str], i: int) -> str:
"""
Returns a string, where replacing sb[i..n) with the smallest possible
letters don't form any palindrome substring.
"""
for j in range(i, len(chars)):
chars[j] = 'a'
while self._containsPalindrome(chars, j):
chars[j] = chr(ord(chars[j]) + 1)
return ''.join(chars) # code by PROGIEZ
