problemeasyalgorithmsleetcode-2027leetcode 2027leetcode2027

Minimum Moves to Convert String

EasyUpdated: Aug 2, 2025
Practice on:
LeetCode

Problem

You are given a string s consisting of n characters which are either 'X' or 'O'.

A move is defined as selecting three consecutive characters of s and converting them to 'O'. Note that if a move is applied to the character 'O', it will stay the same.

Return _theminimum number of moves required so that all the characters of _s are converted to'O'.

Examples

Example 1

Input: s = "XXX"
Output: 1
Explanation: _XXX_ -> OOO
We select all the 3 characters and convert them in one move.

Example 2

Input: s = "XXOX"
Output: 2
Explanation: _XXO_ X -> O _OOX_ -> OOOO
We select the first 3 characters in the first move, and convert them to 'O'.
Then we select the last 3 characters and convert them so that the final string contains all 'O's.

Example 3

Input: s = "OOOO"
Output: 0
Explanation: There are no 'X's in s to convert.

Constraints

  • 3 <= s.length <= 1000
  • s[i] is either 'X' or 'O'.

Solution

Method 1 – Greedy Jump

Intuition

To minimize moves, whenever we see an 'X', we convert it and the next two characters to 'O' in one move, then skip ahead by three. This ensures every 'X' is covered with the fewest moves.

Approach

  1. Initialize a counter for moves and a pointer at the start of the string.
  2. While the pointer is within the string:
    • If the current character is 'X', increment the move counter and skip the next two characters (move pointer by 3).
    • Otherwise, move the pointer by 1.
  3. Return the move counter.

Code

C++
class Solution {
public:
    int minimumMoves(string s) {
        int ans = 0, i = 0, n = s.size();
        while (i < n) {
            if (s[i] == 'X') {
                ans++;
                i += 3;
            } else {
                i++;
            }
        }
        return ans;
    }
};
Go
func minimumMoves(s string) int {
    ans, i, n := 0, 0, len(s)
    for i < n {
        if s[i] == 'X' {
            ans++
            i += 3
        } else {
            i++
        }
    }
    return ans
}
Java
class Solution {
    public int minimumMoves(String s) {
        int ans = 0, i = 0, n = s.length();
        while (i < n) {
            if (s.charAt(i) == 'X') {
                ans++;
                i += 3;
            } else {
                i++;
            }
        }
        return ans;
    }
}
Kotlin
class Solution {
    fun minimumMoves(s: String): Int {
        var ans = 0
        var i = 0
        val n = s.length
        while (i < n) {
            if (s[i] == 'X') {
                ans++
                i += 3
            } else {
                i++
            }
        }
        return ans
    }
}
Python
def minimum_moves(s: str) -> int:
    ans, i, n = 0, 0, len(s)
    while i < n:
        if s[i] == 'X':
            ans += 1
            i += 3
        else:
            i += 1
    return ans
Rust
impl Solution {
    pub fn minimum_moves(s: String) -> i32 {
        let s = s.as_bytes();
        let mut ans = 0;
        let mut i = 0;
        let n = s.len();
        while i < n {
            if s[i] == b'X' {
                ans += 1;
                i += 3;
            } else {
                i += 1;
            }
        }
        ans
    }
}
TypeScript
class Solution {
    minimumMoves(s: string): number {
        let ans = 0, i = 0, n = s.length;
        while (i < n) {
            if (s[i] === 'X') {
                ans++;
                i += 3;
            } else {
                i++;
            }
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of s. Each character is checked at most once.
  • 🧺 Space complexity: O(1), only a few variables are used for tracking the answer.

Comments