Scale Engineer

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:

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

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.

Solutions

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 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 →

Next problem