Minimum Moves to Convert String

easy string greedy

Problem

You are given a string s consisting only of 'X' and 'O'. In one move you may pick any three consecutive characters and turn all of them into 'O'. Return the minimum number of moves required to convert s into all 'O'.

Inputs = "XXOX"

Output2

Convert s[0..2] then s[1..3] (or any equivalent). Greedily jumping by 3 on each X also yields 2.

s (only X and O)

def minimum_moves(s):
    moves = 0
    i = 0
    while i < len(s):
        if s[i] == 'X':
            moves += 1
            i += 3
        else:
            i += 1
    return moves

function minimumMoves(s) {
  let moves = 0;
  let i = 0;
  while (i < s.length) {
    if (s[i] === 'X') {
      moves++;
      i += 3;
    } else {
      i++;
    }
  }
  return moves;
}

class Solution {
    public int minimumMoves(String s) {
        int moves = 0, i = 0;
        while (i < s.length()) {
            if (s.charAt(i) == 'X') {
                moves++;
                i += 3;
            } else {
                i++;
            }
        }
        return moves;
    }
}

int minimumMoves(string s) {
    int moves = 0, i = 0;
    while (i < (int)s.size()) {
        if (s[i] == 'X') {
            moves++;
            i += 3;
        } else {
            i++;
        }
    }
    return moves;
}

Explanation

This is a greedy problem. Each move paints a window of three characters into O, and the smart move is always to line up that window so it starts on the first X you see.

We scan left to right with index i. When we hit an 'X', we must use a move to clean it. That one move can also cover the next two characters, so we count the move and jump ahead by 3 with i += 3.

If the current character is already 'O', there is nothing to fix here, so we just step forward by one. We never need to start a window earlier, because painting always reaches forward — covering later characters for free.

Example: s = "XXOX". At index 0 we see X, count a move, jump to index 3. There we see another X, count a second move, jump past the end. Total moves: 2.

Time: O(n) Space: O(1)