Skip to main content
Talentd

Minimum Moves to Convert String - Solution & Explanation

EasyStringGreedy13 min readAsked at: Google, Bloomberg, Jeavio
Practice this problem

Problem Statement

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

Approach Overview

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.

Approach 1: Greedy Approach

The greedy approach involves scanning through the string, and whenever an 'X' is encountered, converting three consecutive characters to 'O'. This method ensures that each move is used optimally, converting the maximum number of characters possible in a single move to minimize the total count.

This C solution defines a function minimumMoves that iterates over the string. When an 'X' is found, it increments the move counter and jumps forward by 3 indices to apply the conversion.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(1), as no additional space is used other than a few variables.

Try this approach in the editor →

Approach 2: Recursive Backtracking (Inefficient)

Though not the most optimal solution, a recursive backtracking method can explore all possibilities. This checks all potential moves, backtracks when necessary, and might help understand the problem domain and provide a deterministic method if implemented carefully with memoization.

The recursive version examines each index and decides whether to convert based on the presence of 'X'. Moves are incremented recursively down the string.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), but with recursion overhead.
Space Complexity: O(n), due to call stack with recursion.

Try this approach in the editor →

Approach 3: Greedy Algorithm

Traverse the string s. Whenever you encounter 'X', move the pointer i three steps forward and add 1 to the answer; otherwise, move the pointer i one step forward.

The time complexity is O(n), where n represents the length of the string s.

Code

PythonJavaC++GoTypeScriptRustC

Python

Java

C++

Go

TypeScript

Rust

C

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Greedy Approach

Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(1), as no additional space is used other than a few variables.

Recursive Backtracking (Inefficient)

Time Complexity: O(n), but with recursion overhead.
Space Complexity: O(n), due to call stack with recursion.

Greedy Algorithm—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Recursive Backtracking (Inefficient)O(3^n)O(n)Useful for understanding the brute-force search space or explaining why optimization is required
Greedy ScanO(n)O(1)Best choice for interviews and production code; processes the string in one pass

Video Solution

2027. Minimum Moves to Convert String | LEETCODE EASY • code Explainer • 1,159 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Minimum Moves to Convert String easy or hard?
Minimum Moves to Convert String is classified as an Easy problem on LeetCode with an acceptance rate around 57%. The main challenge is recognizing the greedy observation that converting the earliest 'X' immediately always leads to the optimal solution.
Minimum Moves to Convert String Python/Java solution
Most implementations follow the same greedy pattern. Loop through the string, increment the answer when encountering 'X', and advance the pointer by three positions. The logic is identical across Python, Java, C++, C#, and JavaScript because it relies only on basic string indexing.
How to solve Minimum Moves to Convert String in O(n)?
Iterate through the string with an index pointer. When the current character is 'X', increment the move counter and jump the index forward by 3 because a single operation converts positions i, i+1, and i+2 to 'O'. If the character is 'O', simply move to the next index. This single pass guarantees O(n) time complexity.
What is the best approach for Minimum Moves to Convert String?
The greedy approach is the best solution. Scan the string from left to right, and whenever you encounter an 'X', perform one move that converts that character and the next two positions to 'O'. Then skip the next two indices because they are already handled. This produces the minimum number of moves in O(n) time and O(1) space.
Is Minimum Moves to Convert String asked at Google/Amazon/Meta?
Greedy string scanning problems like this frequently appear in interviews at companies such as Amazon, Google, and Meta because they test pattern recognition and the ability to derive optimal local decisions. Variants of window-based greedy problems are especially common in coding interviews.
What data structure is used in Minimum Moves to Convert String?
The problem mainly operates on a string and does not require additional data structures. The optimal solution uses a greedy pointer-based traversal of the string and a simple counter to track the number of moves.
What is the time complexity of Minimum Moves to Convert String?
The optimal greedy solution runs in O(n) time because each character in the string is processed at most once during the linear scan. The space complexity is O(1) since only a counter and an index pointer are used without extra data structures.

Ready to solve this problem?

Practice Minimum Moves to Convert String with our built-in code editor and test cases.

Practice on FleetCode
Previous

Minimum Cost to Convert String I

Next

Minimum Cost to Convert String II