Minimum Moves to Convert String — LeetCode 2027 Python Solution

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

Example

Input

s = "XXX"

Output

1

Explanation

XXX -> OOO

Python solution

class Solution:
    def minimumMoves(self, s: str) -> int:
        ans = i = 0
        while i < len(s):
            if s[i] == "X":
                ans += 1
                i += 3
            else:
                i += 1
        return ans

Complexity

Pattern: Greedy

Take the locally best option every time — when you can prove that never costs you later. LeetCode 2027. Minimum Moves to Convert String is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Greedy.

The greedy guide has the Python template for the pattern and the 346 LeetCode problems that use it.

Related problems