We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Moves to Convert String

Number: 2154

Difficulty: Easy

Paid? No

Companies: Jeavio

Problem Description

Given a string s consisting of characters 'X' and 'O', the task is to convert all characters to 'O' using the minimum number of moves. In one move, you can select any three consecutive characters and convert them all to 'O'. The goal is to determine the minimum number of moves required to achieve a string of all 'O's.

Key Insights

  • A greedy approach works because converting three consecutive characters maximizes the number of 'X's turned to 'O's in one move.
  • When an 'X' is encountered, applying a move starting at that index will set the next two characters to 'O', so you can skip the next two characters.
  • If encountered spans of 'O's, you simply move to the next character.
  • Moving the pointer by three after converting saves redundant operations.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string since we iterate through the string once. Space Complexity: O(1), as only a few variables are used.

Solution

The solution employs a greedy algorithm. Traverse the string from left to right using an index pointer. Each time an 'X' is encountered, apply a move (simulate by incrementing the counter) and skip the next two characters because they are guaranteed to be changed to 'O' by this move. This ensures that each move covers as many 'X's as possible. The pointer skips ahead by three positions after each move. If the character is 'O', simply move to the next character.

Code Solutions

# Python solution

def minimumMoves(s: str) -> int:
    moves = 0  # count number of moves
    i = 0  # pointer to iterate through the string
    while i < len(s):
        # If the current character is 'X', perform a move and skip next two characters
        if s[i] == 'X':
            moves += 1  # Increment the move counter
            i += 3  # Skip next two characters as move covers three consecutive positions
        else:
            i += 1  # Move to the next character if it's already 'O'
    return moves

# Example usage:
# print(minimumMoves("XXOX"))
← Back to All Questions