Minimum Moves to Convert String solution and explanation
Google
9 more videos on this problem
2027. Minimum Moves to Convert String | LEETCODE EASYcode Explainer · 4:57 · 1K views
2027. Minimum Moves to Convert String (Leetcode Easy)Programming Live with Larry · 3:52 · 1K views
Minimum Moves to Convert String | Leetcode 2027 | Approach + Code with explanation.Pirai's Academy · 6:14 · 336 views
LeetCode 2027 | Minimum Moves to Convert String | JavaSleepy Cracker · 1:41 · 236 views
Leetcode solving 2027. Minimum Moves to Convert StringMath Geeks · 3:16 · 157 views
Minimum Moves to Convert String || 5 October leetcode solution || today leetcode solution |leetcodeProgramming languages by shuklaclasses · 0:22 · 119 views
2027. Minimum Moves to Convert String - JavaScript - 1 LineAlgoPrepMaster · 0:48 · 41 views
LeetCode Problem 2027. Minimum Moves to Convert String - SwiftiOSxBank · 5:32 · 24 views
Minimum Moves to Convert String | LeetCode 2027 | Greedy Approach Explained in C++Jilan DEV · 4:45 · 7 views
LeetCode 2027: Minimum Moves to Convert StringAlitaCode · 23:45 · 3 views
The problem
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'sinsto convert.
Constraints:
3 <= s.length <= 1000s[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.
def minimum_moves(s: str) -> int:
moves = 0
i = 0
while i < len(s):
if s[i] == 'X':
moves += 1
i += 3
else:
i += 1
return moves
# Example usage
s = "XXOX"
print(minimum_moves(s)) # Output: 2public class MinMoves {
public static int minimumMoves(String s) {
int moves = 0;
int i = 0;
while (i < s.length()) {
if (s.charAt(i) == 'X') {
moves++;
i += 3;
} else {
i++;
}
}
return moves;
}
public static void main(String[] args) {
String s = "XXOX";
System.out.println(minimumMoves(s)); // Output: 2
}
}#include <iostream>
using namespace std;
int minimumMoves(string s) {
int moves = 0;
int i = 0;
while (i < s.length()) {
if (s[i] == 'X') {
moves++;
i += 3;
} else {
i++;
}
}
return moves;
}
int main() {
string s = "XXOX";
cout << minimumMoves(s) << endl; // Output: 2
return 0;
}function minimumMoves(s) {
let moves = 0;
let i = 0;
while (i < s.length) {
if (s[i] === 'X') {
moves++;
i += 3;
} else {
i++;
}
}
return moves;
}
// Example usage
const s = "XXOX";
console.log(minimumMoves(s)); // Output: 2;#include <stdio.h>
#include <string.h>
int minimumMoves(char *s) {
int moves = 0;
int i = 0;
while (i < strlen(s)) {
if (s[i] == 'X') {
moves++;
i += 3;
} else {
i++;
}
}
return moves;
}
int main() {
char s[] = "XXOX";
printf("%d\n", minimumMoves(s)); // Output: 2
return 0;
}using System;
class MinMoves {
public static int MinimumMoves(string s) {
int moves = 0;
int i = 0;
while (i < s.Length) {
if (s[i] == 'X') {
moves++;
i += 3;
} else {
i++;
}
}
return moves;
}
static void Main() {
string s = "XXOX";
Console.WriteLine(MinimumMoves(s)); // Output: 2
}
}In the Python implementation, the string is iterated through index i. When 'X' is encountered, it increments moves and skips the subsequent 2 characters (total 3 positions).
Time Complexity: O(n), one complete pass through the string.
Space Complexity: O(1), in-place calculation of moves only.
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.
def min_moves_recursive(s: str, index: int) -> int:
if index >= len(s):
return 0
if s[index] == 'O':
return min_moves_recursive(s, index + 1)
return 1 + min_moves_recursive(s, index + 3)
# Example usage
s = "XXOX"
print(min_moves_recursive(s, 0)) # Output: 2public class MinMovesRecursive {
public static int minMovesRecursive(String s, int index) {
if (index >= s.length())
return 0;
if (s.charAt(index) == 'O')
return minMovesRecursive(s, index + 1);
return 1 + minMovesRecursive(s, index + 3);
}
public static void main(String[] args) {
String s = "XXOX";
System.out.println(minMovesRecursive(s, 0)); // Output: 2
}
}#include <iostream>
#include <string>
using namespace std;
int minMovesRecursive(const string &s, int index) {
if (index >= s.size())
return 0;
if (s[index] == 'O')
return minMovesRecursive(s, index + 1);
return 1 + minMovesRecursive(s, index + 3);
}
int main() {
string s = "XXOX";
cout << minMovesRecursive(s, 0) << endl; // Output: 2
return 0;
}function minMovesRecursive(s, index) {
if (index >= s.length) return 0;
if (s[index] === 'O') return minMovesRecursive(s, index + 1);
return 1 + minMovesRecursive(s, index + 3);
}
// Example usage
const s = "XXOX";
console.log(minMovesRecursive(s, 0)); // Output: 2;#include <stdio.h>
#include <string.h>
int minMovesRecursive(char *s, int index, int len) {
if (index >= len)
return 0;
if (s[index] == 'O')
return minMovesRecursive(s, index + 1, len);
return 1 + minMovesRecursive(s, index + 3, len);
}
int main() {
char s[] = "XXOX";
printf("%d\n", minMovesRecursive(s, 0, strlen(s))); // Output: 2
return 0;
}using System;
class MinMovesRecursive {
public static int MinMovesRecursiveFunc(string s, int index) {
if (index >= s.Length)
return 0;
if (s[index] == 'O')
return MinMovesRecursiveFunc(s, index + 1);
return 1 + MinMovesRecursiveFunc(s, index + 3);
}
static void Main() {
string s = "XXOX";
Console.WriteLine(MinMovesRecursiveFunc(s, 0)); // Output: 2
}
}This Python function follows a simple recursive check on each index, applying conversion moves when necessary.
Time Complexity: O(n) with function stack overhead.
Space Complexity: O(n) due to recursion depth.
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.
function minimumMoves(s: string): number {
const n = s.length;
let ans = 0;
let i = 0;
while (i < n) {
if (s[i] === 'X') {
ans++;
i += 3;
} else {
i++;
}
}
return ans;
}func minimumMoves(s string) (ans int) {
for i := 0; i < len(s); i++ {
if s[i] == 'X' {
ans++
i += 2
}
}
return
}impl Solution {
pub fn minimum_moves(s: String) -> i32 {
let s = s.as_bytes();
let n = s.len();
let mut ans = 0;
let mut i = 0;
while i < n {
if s[i] == b'X' {
ans += 1;
i += 3;
} else {
i += 1;
}
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Greedy Approach | Time Complexity: O(n), one complete pass through the string. |
| Recursive Backtracking (Inefficient) | Time Complexity: O(n) with function stack overhead. |
| Greedy Algorithm | – |
Complexity analysis
| Approach | Time | Space | When 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 Scan | O(n) | O(1) | Best choice for interviews and production code; processes the string in one pass |
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.