Watch 10 video solutions for Minimum Operations to Transform String, a medium level problem involving String, Greedy. This walkthrough by Sanyam IIT Guwahati has 295 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
'y' to 'z' to get "zz".'z' to 'a' to get "aa".Example 2:
Input: s = "a"
Output: 0
Explanation:
"a" only consists of 'a'āāāāāāā characters. Thus, the answer is 0.
Constraints:
1 <= s.length <= 5 * 105s consists only of lowercase English letters.Problem Overview: You are given two strings and need the minimum number of operations required to transform the source string into the target string. Instead of fixing characters one by one, an operation can fix a contiguous segment, so the goal is to minimize how many such segments you apply.
Approach 1: Naive Simulation (O(nĀ²) time, O(1) space)
A straightforward idea is to scan the string and try applying an operation starting at every mismatched index. For each position, expand forward while characters differ and simulate fixing that range. This repeatedly scans portions of the string, which leads to nested iteration. The approach works for small inputs but becomes inefficient because every mismatch can trigger another scan of the remaining substring.
Approach 2: Greedy Single Pass (O(n) time, O(1) space)
The optimal solution comes from a simple observation: a single operation can fix an entire continuous block of mismatched characters. Instead of fixing characters individually, count how many mismatch segments exist. Iterate through both strings once. When s[i] != t[i] and either i == 0 or the previous characters already matched, you have discovered the start of a new segment and must perform one operation. Continue scanning until the mismatch block ends.
This greedy approach works because extending an operation across an already mismatched block never increases the cost. Treat each contiguous mismatch region as one operation and count them during a single traversal. The algorithm only performs constant work per character, making it linear and memory efficient.
Implementation is straightforward: iterate with an index, compare characters, and increment a counter when a new mismatch block begins. This pattern appears frequently in string problems where operations affect contiguous ranges and the optimal strategy is to compress adjacent work into one step. The reasoning also follows classic greedy logic: make the locally optimal decision (start an operation at the first mismatch) and extend it as far as possible.
Recommended for interviews: Interviewers expect the greedy single-pass solution. The naive simulation demonstrates baseline reasoning, but recognizing that consecutive mismatches can be grouped into a single operation shows strong pattern recognition in string traversal problems.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Naive Simulation | O(nĀ²) | O(1) | Conceptual baseline when first reasoning about mismatch segments |
| Greedy Single Pass | O(n) | O(1) | Optimal approach for large strings and typical interview solutions |