Skip to content

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] and s2[i] when the characters from 'a' to 'z' are placed in a cyclic order, for all i 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

Thinking

A character may move around the alphabet ring at a total cost of at most \(k\), and the string should become lexicographically smallest. A global search over remaining budget grows with both position and \(k\).

Lexicographic order is decided from the left, so shrinking a prefix as much as possible never hurts later positions. The cheapest ring distance from \(c_1\) to a smaller \(c_2\) is \(\min(c_1-c_2,\,26-(c_1-c_2))\).

From left to right, try letters smaller than the current one and take the cheapest feasible change, then subtract its cost from \(k\). The alphabet has size \(26\), so the inner enumeration is constant.

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
class Solution:
    def getSmallestString(self, s: str, k: int) -> str:
        cs = list(s)
        for i, c1 in enumerate(s):
            for c2 in ascii_lowercase:
                if c2 >= c1:
                    break
                d = min(ord(c1) - ord(c2), 26 - ord(c1) + ord(c2))
                if d <= k:
                    cs[i] = c2
                    k -= d
                    break
        return "".join(cs)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
    public String getSmallestString(String s, int k) {
        char[] cs = s.toCharArray();
        for (int i = 0; i < cs.length; ++i) {
            char c1 = cs[i];
            for (char c2 = 'a'; c2 < c1; ++c2) {
                int d = Math.min(c1 - c2, 26 - c1 + c2);
                if (d <= k) {
                    cs[i] = c2;
                    k -= d;
                    break;
                }
            }
        }
        return new String(cs);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
public:
    string getSmallestString(string s, int k) {
        for (int i = 0; i < s.size(); ++i) {
            char c1 = s[i];
            for (char c2 = 'a'; c2 < c1; ++c2) {
                int d = min(c1 - c2, 26 - c1 + c2);
                if (d <= k) {
                    s[i] = c2;
                    k -= d;
                    break;
                }
            }
        }
        return s;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
func getSmallestString(s string, k int) string {
    cs := []byte(s)
    for i, c1 := range cs {
        for c2 := byte('a'); c2 < c1; c2++ {
            d := int(min(c1-c2, 26-c1+c2))
            if d <= k {
                cs[i] = c2
                k -= d
                break
            }
        }
    }
    return string(cs)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
function getSmallestString(s: string, k: number): string {
    const cs: string[] = s.split('');
    for (let i = 0; i < s.length; ++i) {
        for (let j = 97; j < s[i].charCodeAt(0); ++j) {
            const d = Math.min(s[i].charCodeAt(0) - j, 26 - s[i].charCodeAt(0) + j);
            if (d <= k) {
                cs[i] = String.fromCharCode(j);
                k -= d;
                break;
            }
        }
    }
    return cs.join('');
}

Comments