Minimum Moves to Convert String

Easy
847.

Minimum Moves to Convert String

Minimum Moves to Convert String is an easy coding problem on strings and greedy, asked in Amazon, Microsoft and Cognizant interviews.

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'
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @return {number}
 */
var minimumMoves = function(s) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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

Hints for Minimum Moves to Convert String

  1. Hint 1

    Scan left to right: the leftmost remaining 'X' has to be covered by some move.

  2. Hint 2

    The best move covering it starts exactly at it — starting earlier wastes coverage to the left.

  3. 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

  1. Walk i over the string.
  2. On 'O', advance by one.
  3. 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

Java

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