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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimum Moves to Convert String

Difficulty: Easy

Problem Description

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

Key Insights

  • Each move can convert three consecutive 'X's to 'O's.
  • Overlapping moves can optimize the number of moves required.
  • The problem can be solved by a greedy approach, processing the string from left to right.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

The solution involves iterating through the string while counting the number of moves needed. Whenever three consecutive 'X's are found, they can all be converted in one move, and we can skip to the next part of the string that hasn't been converted yet. This greedy approach ensures we minimize the number of moves.

Code Solutions

def minimumMoves(s: str) -> int:
    moves = 0
    i = 0
    while i < len(s):
        if s[i] == 'X':
            moves += 1  # We will make a move
            i += 3  # Skip the next two characters as they are converted too
        else:
            i += 1  # Move to the next character
    return moves
← Back to All Questions