# Minimum Moves to Convert String
**Difficulty:** EASY
[External](https://leetcode.com/problems/minimum-moves-to-convert-string)
Canonical: https://scaleengineer.com/dsa/problems/minimum-moves-to-convert-string
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** String
---
## 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 _the **minimum** number of moves required so that all the characters of_ `s` _are converted to_ `'O'`.

**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:** XXOX -> OOOX -> 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'`.

# Approaches
## Dynamic Programming
This approach uses dynamic programming to solve the problem by breaking it down into smaller, overlapping subproblems. We define a DP array `dp[i]` to store the minimum number of moves required to convert the suffix of the string starting at index `i` to all 'O's. By computing the values for `dp[i]` from the end of the string to the beginning, we can find the solution for the entire string at `dp[0]`.
**Time:** O(N), where N is the length of the string. We iterate through the string once to fill the DP table. · **Space:** O(N), where N is the length of the string. This is for the DP array used to store the results of subproblems.
**Pros:** Provides a structured and clear way to arrive at the optimal solution.; The logic can be easily understood through the recurrence relation.
**Cons:** Uses O(N) extra space for the DP array, which is less optimal than the greedy approach.
### Explanation
In this approach, we define `dp[i]` as the minimum number of moves to make the suffix `s[i...n-1]` consist of only 'O's. Our goal is to compute `dp[0]`.

The base cases for our recurrence are the states beyond the end of the string. An empty suffix requires zero moves, so `dp[n] = dp[n+1] = dp[n+2] = 0`.

We can build our solution by iterating backwards from `i = n-1` down to `0`. For each index `i`, we decide the minimum moves based on the character `s[i]`:
- If `s[i]` is 'O', no move is needed at this position. The problem is reduced to solving for the suffix starting at `i+1`. Thus, `dp[i] = dp[i+1]`.
- If `s[i]` is 'X', we must perform a move to convert it. The most effective strategy is to apply the move on the three consecutive characters `s[i...i+2]`. This single move handles `s[i]` and potentially other 'X's at `i+1` and `i+2`. After this move, the subproblem is reduced to making the suffix from `i+3` onwards all 'O's. The total moves would be `1 + dp[i+3]`.

The final answer is `dp[0]`. This logic can be implemented using a bottom-up DP table or a top-down recursive approach with memoization.

Here is the code for the bottom-up DP approach:
```java
class Solution {
    public int minimumMoves(String s) {
        int n = s.length();
        int[] dp = new int[n + 3];
        
        for (int i = n - 1; i >= 0; i--) {
            if (s.charAt(i) == 'O') {
                dp[i] = dp[i + 1];
            } else {
                dp[i] = 1 + dp[i + 3];
            }
        }
        return dp[0];
    }
}
```
### Algorithm
- Create a DP array `dp` of size `n + 3`, where `n` is the length of the string. Initialize all its values to 0.
- Iterate with an index `i` from `n - 1` down to `0`.
- At each index `i`, check the character `s.charAt(i)`:
  - If `s.charAt(i) == 'O'`, it means no new move is required at this position. The number of moves is the same as for the subproblem starting at `i+1`. So, set `dp[i] = dp[i+1]`.
  - If `s.charAt(i) == 'X'`, a move must be made to cover this 'X'. The greedy choice is to apply a move starting at `i`, which covers `s[i...i+2]`. This costs 1 move, plus the moves required for the rest of the string, which starts at `i+3`. So, set `dp[i] = 1 + dp[i+3]`.
- After the loop finishes, `dp[0]` will hold the minimum number of moves for the entire string. Return `dp[0]`.

## Greedy Single-Pass Approach
A more efficient approach is to use a greedy strategy. We can iterate through the string from left to right. Whenever we encounter an 'X', we know a move is necessary. The best greedy choice is to make a move that covers the current 'X' and the next two characters. This is because it resolves the current 'X' while making the most progress possible, potentially converting future 'X's in the same move. After making a move, we can skip the next two characters since they are now guaranteed to be 'O's.
**Time:** O(N), where N is the length of the string. We perform a single pass through the string. · **Space:** O(1). We only use a few variables to store the count of moves and the current index, which does not depend on the input string size.
**Pros:** Highly efficient with O(1) space complexity.; Simple to understand and implement.; Optimal solution in terms of both time and space.
**Cons:** The correctness of the greedy choice might not be immediately obvious without a formal proof, although it is intuitive for this problem.
### Explanation
The core idea of the greedy approach is that when we scan the string from left to right and find the first 'X' at index `i`, we must use a move to convert it. To be most efficient, we should apply a move that covers this 'X' and extends as far to the right as possible. This move covers indices `i`, `i+1`, and `i+2`.

By applying the move at `s[i...i+2]`, we ensure that `s[i]` becomes 'O'. This is the most 'forward-looking' move, as it clears the current problem ('X' at `i`) and potentially resolves future problems at `i+1` and `i+2` at no extra cost. After this move, these three positions are all 'O's, so we can confidently continue our scan from index `i+3`.

We can implement this by iterating through the string with an index. If we see an 'X', we count it as one move and jump our index forward by 3. If we see an 'O', we just move to the next character.

Here is the code for the greedy approach:
```java
class Solution {
    public int minimumMoves(String s) {
        int moves = 0;
        int i = 0;
        int n = s.length();
        while (i < n) {
            if (s.charAt(i) == 'X') {
                moves++;
                i += 3;
            } else {
                i++;
            }
        }
        return moves;
    }
}
```
### Algorithm
- Initialize a variable `moves` to 0 and an index `i` to 0.
- Use a `while` loop to iterate as long as `i` is less than the string length `n`.
- Inside the loop, check the character at the current index `i`:
  - If `s.charAt(i)` is 'X', it means we need to perform a move. Increment `moves` by 1. Since a move converts three characters (`i`, `i+1`, `i+2`), we can skip the next two positions. Advance the index `i` by 3.
  - If `s.charAt(i)` is 'O', no move is needed for this character. Simply advance the index `i` by 1.
- After the loop terminates, `moves` will hold the minimum number of moves required. Return `moves`.

# Solutions
### Java

```java
class Solution {
public
  int minimumMoves(String s) {
    int ans = 0;
    for (int i = 0; i < s.length(); ++i) {
      if (s.charAt(i) == 'X') {
        ++ans;
        i += 2;
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minimumMoves(string s) {
    int ans = 0;
    for (int i = 0; i < s.size(); ++i) {
      if (s[i] == 'X') {
        ++ans;
        i += 2;
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def minimumMoves(self, s: str) -> int: ans = i = 0 while i < len(s): if s[i] == "X": ans += 1 i += 3 else: i += 1 return ans

```