Minimum Moves to Convert String

Difficulty: Easy | Acceptance: 57.90% | Paid: No Topics: String, Greedy

You are given a string s consisting only of the characters ‘X’ and ‘O’.

In one move, you can select exactly three consecutive characters of s and convert them to ‘O’. Note that if a character is already ‘O’, it remains ‘O’.

Return the minimum number of moves required so that all the characters of s are converted to ‘O’.

• Examples
• Constraints
• Greedy (Left-to-Right)
• Greedy (Right-to-Left)
• Simulation with String Modification

Examples

Example 1

Input: s = "XXX"
Output: 1
Explanation: We can convert the substring "XXX" in one move.

Example 2

Input: s = "XXOX"
Output: 2
Explanation: We can convert "XXO" to "OOO" in the first move. Then convert "OX" to "OO" in the second move.

Example 3

Input: s = "OOOO"
Output: 0
Explanation: There are no 'X's to convert.

Constraints

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

Greedy (Left-to-Right)

Intuition Always start converting from the leftmost ‘X’ to minimize overlap with future conversions.

Steps

• Iterate through the string from left to right
• When encountering an ‘X’, increment the move count and skip the next two positions
• Continue until the end of the string

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

Complexity

• Time: O(n) where n is the length of the string
• Space: O(1) only using constant extra space
• Notes: Optimal solution with minimal space usage

Greedy (Right-to-Left)

Intuition Similar to left-to-right but traversing from the end, converting ‘X’ by looking at the three characters ending at current position.

Steps

• Iterate through the string from right to left
• When encountering an ‘X’, increment the move count and skip the previous two positions
• Continue until the beginning of the string

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

Complexity

• Time: O(n) where n is the length of the string
• Space: O(1) only using constant extra space
• Notes: Same complexity as left-to-right, just different traversal direction

Simulation with String Modification

Intuition Actually modify the string as we perform conversions, making the process more explicit and intuitive.

Steps

• Convert the string to a mutable data structure
• Iterate through each position
• When finding an ‘X’, increment moves and convert the current and next two positions to ‘O’
• Return the total move count

class Solution:
    def minimumMoves(self, s: str) -> int:
        s = list(s)
        moves = 0
        for i in range(len(s)):
            if s[i] == 'X':
                moves += 1
                for j in range(i, min(i + 3, len(s))):
                    s[j] = 'O'
        return moves

Complexity

• Time: O(n) where n is the length of the string
• Space: O(n) for the mutable copy of the string
• Notes: More intuitive but uses extra space for string modification