Lexicographically Smallest Beautiful String — LeetCode 2663 Python Solution
HardGreedyString
- Problem
- #2663
- Pattern
- Greedy
- Reading time
- 4 min
- Source
- leetcode.com
The problem
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.
Example
- Input
- s = "abcz", k = 26
- Output
- "abda"
- Explanation
- The string "abda" is beautiful and lexicographically larger than the string "abcz".
Python solution
Python
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 ''Complexity
| Measure | Complexity |
|---|---|
| Time | O(n), where n is the length of the string |
| Space | O(1) auxiliary |
Pattern: Greedy
Take the locally best option every time — when you can prove that never costs you later. LeetCode 2663. Lexicographically Smallest Beautiful String is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Greedy.
The greedy guide has the Python template for the pattern and the 346 LeetCode problems that use it.
Related problems
Frequently asked questions
- How hard is LeetCode 2663. Lexicographically Smallest Beautiful String?
- LeetCode 2663. Lexicographically Smallest Beautiful String is rated Hard on LeetCode.
- What is the time complexity of LeetCode 2663. Lexicographically Smallest Beautiful String?
- The Python solution on this page runs in O(n), where n is the length of the string.
- What is the space complexity of LeetCode 2663. Lexicographically Smallest Beautiful String?
- The Python solution on this page uses O(1) auxiliary space.
- What topics does LeetCode 2663. Lexicographically Smallest Beautiful String cover?
- LeetCode 2663. Lexicographically Smallest Beautiful String is tagged Greedy and String on LeetCode.