Minimum Moves to Convert String

Easy

#1845Time: 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.

Patterns

Greedy

Data structures

String

Prompt

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:

'O'

Example 3:

'X's

Constraints:

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

Approaches

2 approaches with complexity analysis and trade-offs.

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

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

Walkthrough

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:

1class Solution {2    public int minimumMoves(String s) {3        int n = s.length();4        int[] dp = new int[n + 3];5        6        for (int i = n - 1; i >= 0; i--) {7            if (s.charAt(i) == 'O') {8                dp[i] = dp[i + 1];9            } else {10                dp[i] = 1 + dp[i + 3];11            }12        }13        return dp[0];14    }15}

Complexity

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.

Trade-offs

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.

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.

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.

Walkthrough

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:

1class Solution {2    public int minimumMoves(String s) {3        int moves = 0;4        int i = 0;5        int n = s.length();6        while (i < n) {7            if (s.charAt(i) == 'X') {8                moves++;9                i += 3;10            } else {11                i++;12            }13        }14        return moves;15    }16}

Complexity

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.

Trade-offs

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.

Solutions

Solution

1class Solution {2public3  int minimumMoves(String s) {4    int ans = 0;5    for (int i = 0; i < s.length(); ++i) {6      if (s.charAt(i) == 'X') {7        ++ans;8        i += 2;9      }10    }11    return ans;12  }13}

1class Solution {2public:3  int minimumMoves(string s) {4    int ans = 0;5    for (int i = 0; i < s.size(); ++i) {6      if (s[i] == 'X') {7        ++ans;8        i += 2;9      }10    }11    return ans;12  }13};

1class Solution:2    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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem