Minimum Moves to Convert String — Problem & Solution
Minimum Moves to Convert String solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Minimum Moves to Convert String is an easy coding problem on strings and greedy, asked in Amazon, Microsoft and Cognizant interviews.
- Difficulty: Easy
- Topics: Strings, Greedy
- Asked at: Amazon, Microsoft, Cognizant
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
s consists of 'X' and 'O'. One move picks any three consecutive characters and turns them all into 'O'.
Return the minimum number of moves needed so that s contains no 'X'.
Example 1
Input: s = "XXX"
Output: 1
Explanation: One move covers all three.
Example 2
Input: s = "XXOX"
Output: 2
Explanation: Cover indices 0–2, then 1–3 (or 3 alone).
Example 3
Input: s = "OOOO"
Output: 0
Constraints
3 <= s.length <= 1000s[i] is 'X' or 'O'
Hints for Minimum Moves to Convert String
Hint 1
Scan left to right: the leftmost remaining
'X'has to be covered by some move.Hint 2
The best move covering it starts exactly at it — starting earlier wastes coverage to the left.
Hint 3
So on seeing an
'X', count a move and skip three characters.
How to solve Minimum Moves to Convert String
A left-to-right greedy. The first 'X' must be covered, and the move that covers it while reaching furthest right is the one starting at that 'X' — so take it and jump past the three characters it blanks.
Approach
- Walk
iover the string. - On
'O', advance by one. - On
'X', count a move and advance by three.
Why it works
Exchange argument: any move covering the leftmost 'X' starts at or before it; sliding it right to start exactly there still covers that 'X' and covers at least as much to the right, so it is never worse. Repeating turns any optimal solution into this greedy.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- Moves may overlap and may run past the end conceptually — the jump of three simply exits the loop.
- Advancing by three on an
'O'skips'X's that still need covering. - The string is guaranteed at least three characters, so a single move always exists.
Reference solution
Python
def minimumMoves(s: str) -> int:
i = ans = 0
while i < len(s):
if s[i] == "X":
ans += 1
i += 3
else:
i += 1
return ansJava
public static int minimumMoves(String s) {
int i = 0, ans = 0;
while (i < s.length()) {
if (s.charAt(i) == 'X') {
ans++;
i += 3;
} else {
i++;
}
}
return ans;
}C++
int minimumMoves(string s) {
int i = 0, ans = 0;
while (i < (int) s.size()) {
if (s[i] == 'X') {
ans++;
i += 3;
} else {
i++;
}
}
return ans;
}JavaScript
var minimumMoves = function(s) {
var i = 0, ans = 0;
while (i < s.length) {
if (s.charAt(i) === "X") { ans++; i += 3; } else i++;
}
return ans;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Greedy Algorithms