Lexicographically Smallest String After Operations With Constraint

Problem

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:

• Thesum 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.

Examples

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.

Solution

Method 1 – Greedy Character Selection

Intuition

To get the lexicographically smallest string t such that the cyclic distance between s and t is at most k, we should try to make each character of t as small as possible, using up the available k budget greedily from left to right.

Approach

1. For each character in s, try to change it to the smallest possible character (from 'a' to 'z') such that the total cost does not exceed k.
2. The cost to change s[i] to c is min(abs(ord(s[i])-ord(c)), 26-abs(ord(s[i])-ord(c))) (cyclic distance).
3. If the cost is within the remaining k, set t[i] to c and subtract the cost from k.
4. If not, keep t[i] as s[i].
5. Continue for all characters.

Code

C++

class Solution {
public:
    string getSmallestString(string s, int k) {
        string t = s;
        for (int i = 0; i < s.size(); ++i) {
            for (char c = 'a'; c <= 'z'; ++c) {
                int d = abs(s[i]-c);
                d = min(d, 26-d);
                if (d <= k) {
                    t[i] = c;
                    k -= d;
                    break;
                }
            }
        }
        return t;
    }
};

Go

func getSmallestString(s string, k int) string {
    b := []byte(s)
    for i := 0; i < len(b); i++ {
        for c := byte('a'); c <= 'z'; c++ {
            d := int(b[i]-c)
            if d < 0 { d = -d }
            if d > 13 { d = 26-d }
            if d <= k {
                b[i] = c
                k -= d
                break
            }
        }
    }
    return string(b)
}

Java

class Solution {
    public String getSmallestString(String s, int k) {
        char[] arr = s.toCharArray();
        for (int i = 0; i < arr.length; i++) {
            for (char c = 'a'; c <= 'z'; c++) {
                int d = Math.abs(arr[i]-c);
                d = Math.min(d, 26-d);
                if (d <= k) {
                    arr[i] = c;
                    k -= d;
                    break;
                }
            }
        }
        return new String(arr);
    }
}

Kotlin

class Solution {
    fun getSmallestString(s: String, k: Int): String {
        val arr = s.toCharArray()
        var rem = k
        for (i in arr.indices) {
            for (c in 'a'..'z') {
                var d = Math.abs(arr[i]-c)
                d = minOf(d, 26-d)
                if (d <= rem) {
                    arr[i] = c
                    rem -= d
                    break
                }
            }
        }
        return String(arr)
    }
}

Python

class Solution:
    def getSmallestString(self, s: str, k: int) -> str:
        ans = []
        for ch in s:
            for c in map(chr, range(ord('a'), ord('z')+1)):
                d = abs(ord(ch)-ord(c))
                d = min(d, 26-d)
                if d <= k:
                    ans.append(c)
                    k -= d
                    break
        return ''.join(ans)

Rust

impl Solution {
    pub fn get_smallest_string(s: String, mut k: i32) -> String {
        let mut arr: Vec<u8> = s.bytes().collect();
        for i in 0..arr.len() {
            for c in b'a'..=b'z' {
                let mut d = (arr[i] as i32 - c as i32).abs();
                d = d.min(26-d);
                if d <= k {
                    arr[i] = c;
                    k -= d;
                    break;
                }
            }
        }
        String::from_utf8(arr).unwrap()
    }
}

TypeScript

class Solution {
    getSmallestString(s: string, k: number): string {
        const arr = s.split('');
        for (let i = 0; i < arr.length; i++) {
            for (let c = 97; c <= 122; c++) {
                let d = Math.abs(arr[i].charCodeAt(0) - c);
                d = Math.min(d, 26-d);
                if (d <= k) {
                    arr[i] = String.fromCharCode(c);
                    k -= d;
                    break;
                }
            }
        }
        return arr.join('');
    }
}

Complexity

• ⏰ Time complexity: O(n*26), where n is the length of s (for each character, we try up to 26 letters).
• 🧺 Space complexity: O(n), for the output string.