Problem Description

You have a string s made up of n characters, where each character is either 'X' or 'O'.

A move consists of selecting three consecutive characters in the string and converting all of them to 'O'. If any of these three characters is already 'O', it remains 'O' after the move.

Your task is to find the minimum number of moves needed to convert all characters in the string to 'O'.

For example:

• If you have "XXX", you can apply one move to convert all three characters to "OOO"
• If you have "XXOX", you could apply one move to positions 0-2 to get "OOOX", then another move to positions 1-3 to get "OOOO" (total: 2 moves)
• If you have "XOX", one move covering all three positions would convert it to "OOO"

The goal is to determine the minimum number of such moves required to make the entire string consist only of 'O' characters.

Intuition

When we encounter an 'X' in the string, we need to convert it to 'O'. Since each move can convert three consecutive characters, the key insight is: once we decide to make a move at a position, we should maximize its effect.

Think about it this way - if we find an 'X' at position i, we have to use at least one move to convert it. We could start our move at position i, i-1, or i-2 (assuming they exist). But here's the clever part: if we start the move at position i, we automatically handle three positions: i, i+1, and i+2.

Why is this greedy approach optimal? Because:

1. Every 'X' must be covered by at least one move
2. When we encounter the leftmost uncovered 'X', we might as well start our move right there
3. Starting the move at this 'X' covers the maximum number of positions to the right that we haven't processed yet

This leads to a simple strategy: scan from left to right. When we hit an 'X', make a move starting at that position (covering 3 characters), then jump ahead by 3 positions since those are all now 'O'. If we hit an 'O', just move to the next position.

The beauty of this approach is that we never need to look back - once we've processed a position, we're done with it. Each 'X' triggers exactly one move that covers it and the next two positions, giving us the minimum number of moves needed.

Learn more about Greedy patterns.

Solution Approach

The implementation uses a greedy algorithm with a simple linear scan through the string. Here's how it works:

We maintain two variables:

• ans: counts the number of moves made
• i: pointer to track our current position in the string

The algorithm follows these steps:

1. Initialize both ans and i to 0

2. Traverse the string using a while loop: while i < len(s)

3. At each position, check the character:

   • If s[i] == "X":
     • Increment the answer by 1 (we're making a move)
     • Jump forward by 3 positions (i += 3) since this move covers positions i, i+1, and i+2
   • If s[i] == "O":
     • Simply move to the next position (i += 1) as no action is needed

4. Return the total number of moves (ans)

The key insight in this implementation is the pointer jump: when we encounter an 'X' and decide to make a move, we skip the next two positions entirely by setting i += 3. This is valid because:

• The move converts all three positions (i, i+1, i+2) to 'O'
• There's no need to check positions i+1 and i+2 since they're guaranteed to be 'O' after the move
• Even if i+1 or i+2 goes beyond the string length, it doesn't matter - the while loop condition will terminate safely

This greedy approach ensures we use the minimum number of moves, with a time complexity of O(n) and space complexity of O(1).

Example Walkthrough

Let's walk through the solution with the string s = "XXOXXX".

Initial state:

• s = "XXOXXX" (length = 6)
• ans = 0 (no moves made yet)
• i = 0 (starting position)

Step 1: i = 0

• Check s[0] = 'X'
• Since it's an 'X', we make a move starting at position 0
• This move covers positions 0, 1, 2, converting "XXO" → "OOO"
• Increment ans = 1 (we made one move)
• Jump forward: i = 0 + 3 = 3
• String state after move: "OOOXXX"

Step 2: i = 3

• Check s[3] = 'X'
• Since it's an 'X', we make a move starting at position 3
• This move covers positions 3, 4, 5, converting "XXX" → "OOO"
• Increment ans = 2 (total of two moves)
• Jump forward: i = 3 + 3 = 6
• String state after move: "OOOOOO"

Step 3: i = 6

• Since i = 6 is not less than len(s) = 6, the loop terminates

Result: We return ans = 2

The algorithm efficiently converted "XXOXXX" to "OOOOOO" in just 2 moves:

• Move 1: positions 0-2
• Move 2: positions 3-5

Notice how we never had to revisit any position - the greedy approach of making a move as soon as we encounter an 'X' and then jumping ahead by 3 positions gives us the optimal solution.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n), where n represents the length of the string s.

The algorithm uses a single while loop that iterates through the string. In each iteration, the index i is incremented by either 1 (when s[i] != "X") or 3 (when s[i] == "X"). In the worst case, when the string contains no "X" characters, the loop will iterate through each character exactly once, resulting in n iterations. In the best case, when all characters are "X" and properly aligned, the loop will iterate approximately n/3 times. Since both cases are linear with respect to the input size, the time complexity is O(n).

Space Complexity: O(1)

The algorithm uses only a constant amount of extra space. The variables ans and i are the only additional storage required, and their space usage does not depend on the input size. The input string s is not modified, and no additional data structures are created during execution.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Attempting to Modify the String In-Place

The Problem: Beginners often try to actually modify the string while traversing it, converting 'X' characters to 'O' after each move. This leads to unnecessary complexity and potential errors.

# INCORRECT approach - trying to modify string
def minimumMoves(s: str) -> int:
    s = list(s)  # Convert to list for mutation
    moves = 0
    i = 0
    while i < len(s):
        if s[i] == 'X':
            # Trying to actually change the characters
            for j in range(i, min(i+3, len(s))):
                s[j] = 'O'
            moves += 1
            i += 1  # Wrong increment!
        else:
            i += 1
    return moves

Why It's Wrong:

• Unnecessarily converts and modifies the string
• After making a move at position i, the code incorrectly increments by 1 instead of 3
• This causes redundant checks and potentially overcounts moves

The Solution: The correct approach doesn't need to modify the string at all. When we encounter an 'X' and decide to make a move, we know that positions i, i+1, and i+2 will all become 'O'. Therefore, we can simply skip ahead by 3 positions without actually changing anything.

Pitfall 2: Incorrectly Handling the Pointer Jump

The Problem: Some might worry about the index going out of bounds when adding 3 to the pointer, leading to defensive but incorrect code:

# INCORRECT - overly defensive boundary checking
def minimumMoves(s: str) -> int:
    moves = 0
    i = 0
    while i < len(s):
        if s[i] == 'X':
            moves += 1
            # Wrong: trying to be "safe" but breaking the logic
            if i + 3 <= len(s):
                i += 3
            else:
                i += 1  # This is incorrect!
        else:
            i += 1
    return moves

Why It's Wrong: When we make a move at position i, we're covering positions i, i+1, and i+2. Even if i+2 is the last character (or beyond), we should still jump by 3 because:

• The move handles all three positions regardless
• If i+3 exceeds the string length, the while loop condition naturally handles termination
• Incrementing by less than 3 would cause us to unnecessarily check positions we've already handled

The Solution: Trust the algorithm's logic. When making a move, always jump by 3. The while loop condition i < len(s) provides all the boundary protection needed.