Skip to content

3675. Minimum Operations to Transform String

SourceWeekly Contest 466 Q2DifficultyMediumRating1414

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

Thinking

One operation advances every occurrence of a chosen letter. The target is the all-\(a\) string, so each non-\(a\) character must walk forward to \(a\).

Operations on the same letter apply in parallel, and the total is the farthest distance to \(a\), i.e. the maximum of \(26-(c-\texttt{a})\).

An all-\(a\) string needs \(0\) operations. One scan records that maximum.

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