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

1
2
3
4

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

Example 2

1
2
3
4
5

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

1
2
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

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;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

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
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

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;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

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
    }
}
1
2
3
4
5
6
7
8
9

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
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

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
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

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.