Minimum Moves to Convert String - Solution & Explanation

Problem Overview: You are given a string consisting of characters 'X' and 'O'. In one move, you can convert three consecutive characters starting from an index into 'O'. The goal is to find the minimum number of moves required to convert the entire string so that no 'X' remains.

Approach 1: Recursive Backtracking (Inefficient) (Time: O(3^n), Space: O(n))

This method explores every possible way to apply conversion moves. At each index containing 'X', the algorithm tries performing a move that flips the current character and the next two positions to 'O'. The recursion continues until the string contains no 'X'. Because multiple overlapping states are explored and the same subproblems repeat frequently, the number of recursive calls grows exponentially. This approach mainly helps you reason about the brute-force search space and understand why a more efficient strategy is needed.

Approach 2: Greedy Approach (Time: O(n), Space: O(1))

The key observation is that when you encounter an 'X', the optimal move is always to convert the current position and the next two characters immediately. Any solution must eventually cover this 'X', and delaying the move never reduces the number of operations. Iterate through the string from left to right. When you see 'X', increment the move counter and skip the next two indices because a single operation already converts them to 'O'. When you see 'O', simply move to the next character. This linear scan ensures each character is processed once, making the algorithm efficient and simple.

The greedy strategy works because every operation affects a fixed window of three characters, and covering the earliest uncovered 'X' immediately always leads to the minimum number of operations. The problem naturally fits a greedy pattern combined with sequential scanning of a string.

Recommended for interviews: The greedy solution is what interviewers expect. It demonstrates that you can identify the local decision that guarantees a global optimum and implement it with a single pass. Mentioning the brute-force or backtracking idea first shows understanding of the problem space, but implementing the O(n) greedy scan shows strong algorithmic judgment.