LeetCode 2027 - Minimum Moves to Convert String

LeetCode Problem 2027

Difficulty: 🟢 Easy
Topics: String, Greedy

Solution

Problem Understanding

The problem asks us to transform a string s containing only characters 'X' and 'O' so that all characters become 'O'. A move consists of selecting three consecutive characters and converting them to 'O'. If a character is already 'O', it remains unchanged. The goal is to determine the minimum number of moves required to achieve this transformation for the entire string.

The input is a string s with length between 3 and 1000 characters, which guarantees that we always have at least three characters to make a move. The output is an integer representing the fewest moves needed to convert all 'X' characters into 'O'.

Key observations include:

1. Only 'X' characters need conversion. 'O' characters do not require action.
2. Each move can potentially convert up to three 'X's at once.
3. Moves can overlap, so optimal placement is important to minimize moves.
4. Edge cases to consider include strings that are already all 'O', strings of only 'X', and strings with scattered 'X's where no three 'X's are contiguous.

Understanding these points ensures the solution does not over-count moves or miss 'X' characters.

Approaches

The brute-force approach would attempt to try every combination of three-character selections until the string is fully converted to 'O'. This is correct because eventually, all 'X's will be covered, but it is highly inefficient, potentially exponential, and unnecessary for the constraints given (up to 1000 characters).

The key insight for a more efficient solution is greedy traversal. Since a move converts three consecutive characters, we can iterate from left to right and, whenever we encounter an 'X', apply a move starting at that position. We then skip the next two characters because they are already converted, ensuring we do not double-count moves. This works because every 'X' must be converted, and the leftmost 'X' determines the earliest possible move.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n)	O(n)	Tries all combinations of moves, too slow for n up to 1000
Optimal	O(n)	O(1)	Greedily converts from left to right, skipping processed characters

Algorithm Walkthrough

1. Initialize a counter moves to 0. This will track the number of moves applied.
2. Start iterating through the string s from left to right using an index i.
3. If s[i] is 'O', increment i by 1 and continue, as no move is required.
4. If s[i] is 'X', increment moves by 1 because we need a move starting at this position.
5. Skip the next two characters by incrementing i by 3, since the current move converts s[i], s[i+1], and s[i+2] to 'O'.
6. Repeat steps 3-5 until the end of the string is reached.
7. Return the total moves as the minimum number of moves required.

Why it works: Every 'X' encountered triggers a move that covers up to three consecutive characters. By skipping the next two characters, we ensure no redundant moves are counted. This greedy approach guarantees the minimum number of moves because every move covers the maximum possible 'X's at that position.

Python Solution

class Solution:
    def minimumMoves(self, s: str) -> int:
        moves = 0
        i = 0
        n = len(s)
        
        while i < n:
            if s[i] == 'X':
                moves += 1
                i += 3  # Skip next two characters as they are converted
            else:
                i += 1
        return moves

The Python implementation follows the algorithm step by step. The variable moves tracks the total number of moves. We iterate through the string using i, and whenever we encounter 'X', we increment moves and skip the next two characters because a move covers three characters. Otherwise, we simply continue to the next character.

Go Solution

func minimumMoves(s string) int {
    moves := 0
    n := len(s)
    i := 0
    
    for i < n {
        if s[i] == 'X' {
            moves++
            i += 3 // Skip next two characters
        } else {
            i++
        }
    }
    return moves
}

In Go, the solution is nearly identical to Python. Strings are indexed by byte, which works correctly here because 'X' and 'O' are single-byte characters. The main difference is explicit declaration of variables and type handling, but the algorithm logic remains unchanged.

Worked Examples

Example 1: s = "XXX"

i	s[i]	moves	i increment
0	X	1	0 + 3 = 3

Output: 1 move.

Example 2: s = "XXOX"

i	s[i]	moves	i increment
0	X	1	0 + 3 = 3
3	X	2	3 + 3 = 6

Output: 2 moves.

Example 3: s = "OOOO"

i	s[i]	moves	i increment
0	O	0	0 + 1 = 1
1	O	0	1 + 1 = 2
2	O	0	2 + 1 = 3
3	O	0	3 + 1 = 4

Output: 0 moves.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	We iterate through the string once, skipping characters as needed.
Space	O(1)	Only constant variables are used, no additional data structures.

This solution is linear in time and constant in space, making it efficient even for the upper limit of n = 1000.

Test Cases

# Provided examples
assert Solution().minimumMoves("XXX") == 1  # all Xs in a group
assert Solution().minimumMoves("XXOX") == 2  # scattered Xs
assert Solution().minimumMoves("OOOO") == 0  # no Xs

# Additional test cases
assert Solution().minimumMoves("X") == 1  # single X
assert Solution().minimumMoves("OXO") == 1  # single X in the middle
assert Solution().minimumMoves("XXXXX") == 2  # consecutive Xs more than 3
assert Solution().minimumMoves("OXOXOX") == 2  # alternating X and O
assert Solution().minimumMoves("OOOOOXOOX") == 2  # scattered Xs with O gaps

Test	Why
"XXX"	Converts a full group of three Xs in one move
"XXOX"	Handles Xs at start and end, requiring two moves
"OOOO"	No moves needed if no Xs present
"X"	Single character, less than three
"OXO"	Single X in the middle of Os
"XXXXX"	Overlapping moves required for consecutive Xs
"OXOXOX"	Alternating pattern requires multiple moves
"OOOOOXOOX"	Scattered Xs with Os between

Edge Cases

Single 'X' at the end or beginning: The move still covers three characters, so even if fewer than three remain, a single move counts. Implementation handles this because we increment moves and skip i += 3 regardless of string length.

All characters 'O': No moves are needed. The loop increments i by 1 each time, but moves remains zero. This ensures no false positives.

Alternating 'X' and 'O': Requires careful skipping to avoid double-counting. The greedy approach ensures we convert the leftmost 'X' first and skip covered characters, giving the minimum moves.