Minimum Moves to Convert String — Easy Problem & Solution

s consists of 'X' and 'O'. One move picks any three consecutive characters and turns them all into 'O'.

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 <= 1000
s[i] is 'X' or 'O'

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 i over 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 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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 282 strings problems · the whole catalogue