3106. Lexicographically Smallest String After Operations With Constraint
Description
You are given a string s
and an integer k
.
Define a function distance(s1, s2)
between two strings s1
and s2
of the same length n
as:
- The sum of the minimum distance between
s1[i]
ands2[i]
when the characters from'a'
to'z'
are placed in a cyclic order, for alli
in the range[0, n - 1]
.
For example, distance("ab", "cd") == 4
, and distance("a", "z") == 1
.
You can change any letter of s
to any other lowercase English letter, any number of times.
Return a string denoting the lexicographically smallest string t
you can get after some changes, such that distance(s, t) <= k
.
Example 1:
Input: s = "zbbz", k = 3
Output: "aaaz"
Explanation:
Change s
to "aaaz"
. The distance between "zbbz"
and "aaaz"
is equal to k = 3
.
Example 2:
Input: s = "xaxcd", k = 4
Output: "aawcd"
Explanation:
The distance between "xaxcd" and "aawcd" is equal to k = 4.
Example 3:
Input: s = "lol", k = 0
Output: "lol"
Explanation:
It's impossible to change any character as k = 0
.
Constraints:
1 <= s.length <= 100
0 <= k <= 2000
s
consists only of lowercase English letters.
Solutions
Solution 1: Enumeration
We can traverse each position of the string $s$. For each position, we enumerate all characters less than the current character, calculate the cost $d$ to change to this character. If $d \leq k$, we change the current character to this character, subtract $d$ from $k$, end the enumeration, and continue to the next position.
After the traversal, we get a string that meets the conditions.
The time complexity is $O(n \times |\Sigma|)$, and the space complexity is $O(n)$. Here, $n$ is the length of the string $s$, and $|\Sigma|$ is the size of the character set. In this problem, $|\Sigma| \leq 26$.
1 2 3 4 5 6 7 8 9 10 11 12 13 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|