Skip to content

3675. Minimum Operations to Transform String

Description

You are given a string s consisting only of lowercase English letters.

You can perform the following operation any number of times (including zero):

  • Choose any character c in the string and replace every occurrence of c with the next lowercase letter in the English alphabet.

Return the minimum number of operations required to transform s into a string consisting of only 'a' characters.

Note: Consider the alphabet as circular, thus 'a' comes after 'z'.

 

Example 1:

Input: s = "yz"

Output: 2

Explanation:

  • Change 'y' to 'z' to get "zz".
  • Change 'z' to 'a' to get "aa".
  • Thus, the answer is 2.

Example 2:

Input: s = "a"

Output: 0

Explanation:

  • The string "a" only consists of 'a'​​​​​​​ characters. Thus, the answer is 0.

 

Constraints:

  • 1 <= s.length <= 5 * 105
  • s consists only of lowercase English letters.

Solutions

Solution 1: Single Pass

According to the problem description, we always start from the character 'b' and successively change each character to the next one until it becomes 'a'. Therefore, we only need to find the character in the string that is farthest from 'a' and calculate its distance to 'a' to get the answer.

The time complexity is \(O(n)\), where \(n\) is the length of the string \(s\). The space complexity is \(O(1)\).

1
2
3
class Solution:
    def minOperations(self, s: str) -> int:
        return max((26 - (ord(c) - 97) for c in s if c != "a"), default=0)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
    public int minOperations(String s) {
        int ans = 0;
        for (char c : s.toCharArray()) {
            if (c != 'a') {
                ans = Math.max(ans, 26 - (c - 'a'));
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
public:
    int minOperations(string s) {
        int ans = 0;
        for (char c : s) {
            if (c != 'a') {
                ans = max(ans, 26 - (c - 'a'));
            }
        }
        return ans;
    }
};

1
2
3
4
5
6
7
8
func minOperations(s string) (ans int) {
    for _, c := range s {
        if c != 'a' {
            ans = max(ans, 26-int(c-'a'))
        }
    }
    return
}

1
2
3
4
5
6
7
8
9
function minOperations(s: string): number {
    let ans = 0;
    for (const c of s) {
        if (c !== 'a') {
            ans = Math.max(ans, 26 - (c.charCodeAt(0) - 97));
        }
    }
    return ans;
}

Comments