Minimum Moves to Convert String

EASY

Description

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

Checkout 2 different approaches to solve Minimum Moves to Convert String. Click on different approaches to view the approach and algorithm in detail.

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

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

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:

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];
    }
}

Complexity Analysis

Time Complexity: O(N), where N is the length of the string. We iterate through the string once to fill the DP table.Space Complexity: O(N), where N is the length of the string. This is for the DP array used to store the results of subproblems.

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Minimum Moves to Convert String. Click on different languages to view the code.

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;
  }
}

Video Solution

Watch the video walkthrough for Minimum Moves to Convert String

Patterns:

Greedy

Data Structures:

String