2027. Minimum Moves to Convert String

EasyGreedyString

Problem Description

You are given a string s which is made up of characters that are either 'X' or 'O'. Your goal is to convert all the characters in the string to 'O' using a specific operation. The operation allows you to select three consecutive characters in the string and change them all to 'O'. If any of those characters are already 'O', they remain 'O'. Your task is to find out the minimum number of such operations required to change every character in the string to 'O'.

Intuition

The solution requires a greedy approach. Start scanning the string from the beginning, and whenever you find an 'X', that means you need to perform the operation because it's the leftmost 'X' that can be converted along with the next two characters. After performing the operation on three characters, you can safely move three positions ahead because those positions are now guaranteed to be 'O'.

This approach reliably finds the minimum number of moves because by always taking the earliest possible operation, you ensure that no move is wasted. If an 'O' is encountered, simply move one position to the right since this position doesn't necessitate the operation. Continue the process until the end of the string. The number of moves made gives the desired result.

Learn more about Greedy patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which of the following is a good use case for backtracking?

Combinatorial problemsRandom number generationTopological sortingMatrix multiplication

I don’t know

Solution Approach

The solution is implemented in a straightforward manner without requiring complex data structures or patterns. Here is a detailed walkthrough of the implementation:

We initialize two variables, ans which will hold the number of moves required, initially set to 0 and i which is our pointer to iterate through the string, initially set to 0.
We use a while loop to iterate over the string until i reaches the end of the string (i < len(s)).
Inside the loop, we check each character of the string. If the current character s[i] is 'X', then a move is required. We increment the ans variable by one to count this move.
Since we can change three consecutive characters with each move, we increment i by 3 after a move is applied (i += 3). This allows us to skip the next two characters because they have been turned into 'O' by the operation, or they were already 'O'.
If the current character s[i] is not 'X' (it's 'O'), then no move is required for these positions. Thus, we move the pointer i by one to check the next character (i += 1).
The loop continues until all characters have been checked.
Finally, the ans variable, which has been accumulating the number of moves required, is returned.

So the important points in the algorithm are:

The use of a greedy approach, always taking the earliest opportunity to perform an operation.
The increment of the pointer based on whether a move was made or not, moving by 3 if a move was performed or by 1 otherwise.

This method ensures that the solution is efficient, with a time complexity of O(n), where n is the length of the string, since each character in the string is considered at most once.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27

1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30

1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

["jk", "mno"]["jm", "kn", "lo"]["jklmnp"]["jm","jn","jo","km","kn","ko","lm","ln","lo"]

I don’t know

Example Walkthrough

Let's say we have the string s = "XXOXOOXOXOOX".

Starting from the left, we encounter 'X' at position 0. We can perform an operation and change s[0:3] from 'XXO' to 'OOO'. We increment our answer to 1 and skip 3 characters to index 3.
At position 3, the character is 'O', so no operation is needed. We increment the index by 1 to move to position 4.
Position 4 is 'X', so we perform an operation on s[4:7], changing 'OOX' to 'OOO'. We increment our answer to 2 and skip 3 characters to index 7.
At position 7, we find another 'X'. We perform the operation on s[7:10], changing 'XOX' to 'OOO'. Increment our answer to 3 and skip 3 characters to index 10.
At position 10, there is an 'X'. Since this is near the end and no more sets of three are available, we perform our final operation on s[10:13] (which is actually just up to s[11] since we've reached the end), changing 'OX' to 'OO'. We increment our answer to 4.

After these steps, the string s is now 'OOOOOOOOOOO', and we used a total of 4 operations. Hence, the minimum number of operations required to change every 'X' to 'O' in s is 4.

Solution Implementation

1class Solution:
2    def minimumMoves(self, grid: str) -> int:
3        # Initialize the number of moves to 0
4        moves_count = 0
5        # Initialize the position index to 0
6        index = 0
7      
8        # Loop through the grid until the end is reached
9        while index < len(grid):
10            # Check if the current character is an 'X'
11            if grid[index] == "X":
12                # If 'X' is found, increase the moves count by 1 since we can flip three consecutive cells
13                moves_count += 1
14                # Move the index 3 cells forward as these cells will be flipped
15                index += 3
16            else:
17                # If the current character is not an 'X', just move to the next cell
18                index += 1
19      
20        # Return the total number of moves needed
21        return moves_count
22

1class Solution {
2    public int minimumMoves(String s) {
3        int moves = 0; // Initialize the count of moves to 0
4      
5        // Loop over the string, increment the loop counter accordingly
6        for (int i = 0; i < s.length(); ++i) {
7            if (s.charAt(i) == 'X') {
8                moves++;  // If the current character is 'X', increment the move count
9                i += 2;   // Skip the next two characters since one move can change up to 3 consecutive characters
10            }
11        }
12      
13        return moves; // Return the total number of moves required
14    }
15}
16

1class Solution {
2public:
3    // Function to count the minimum number of moves required to convert the given string into 'OOO...OOO' (no 'X's)
4    int minimumMoves(string s) {
5        int moveCount = 0; // Variable to store the count of moves
6
7        // Loop through each character in the string
8        for (int i = 0; i < s.size(); ++i) {
9
10            // If the current character is 'X', we need to perform a move
11            if (s[i] == 'X') {
12                ++moveCount;  // Increment the move count
13                i += 2; // Skip the next two characters because a move changes three consecutive characters
14            }
15        }
16
17        // Return the total number of moves required to change all 'X's to 'O's
18        return moveCount;
19    }
20};
21

1/**
2 * Determines the minimum number of moves required to convert the string
3 * so that there are no 'X' characters. Each move can cover up to three consecutive characters.
4 * @param {string} sequence - The string consisting of '.' and 'X' characters.
5 * @return {number} - The minimum number of moves required.
6 */
7function minimumMoves(sequence: string): number {
8    // The length of the string
9    const sequenceLength = sequence.length;
10  
11    // Variable to store the minimum moves
12    let minimumMoves = 0;
13  
14    // Index variable to iterate over the string
15    let index = 0;
16  
17    // Loop through the string
18    while (index < sequenceLength) {
19        // If an 'X' is found, a move is required
20        if (sequence[index] === 'X') {
21            minimumMoves++; // Increment the move counter
22            index += 3; // Skip the next two positions as they are also covered by the move
23        } else {
24            index++; // Move to the next character if current is not 'X'
25        }
26    }
27  
28    // Return the computed minimum moves
29    return minimumMoves;
30}
31

Not Sure What to Study? Take the 2-min Quiz：

Time and Space Complexity

Time Complexity

The time complexity of the given code is O(n), where n is the length of the string s. The while loop iterates through each character of the string at most once. In the worst case, the loop makes n iterations when there are no "X" characters found. In the best case, if "X" characters are found, it skips 3 characters at a time due to i += 3. However, regardless of the pattern of "X" characters within the string, every character is examined no more than once, thereby maintaining a linear time complexity relative to the string length.

Space Complexity

The space complexity of the code is O(1). The function maintains a fixed number of variables (ans and i) that do not scale with the input size. The space used does not depend on the length of the string, therefore it is constant, and no additional data structures are used that would increase the memory usage. Thus, the additional memory required remains constant regardless of the input.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Is the following code DFS or BFS?

1void search(Node root) {
2  if (!root) return;
3  visit(root);
4  root.visited = true;
5  for (Node node in root.adjacent) {
6    if (!node.visited) {
7      search(node);
8    }
9  }
10}

Depth First SearchBreadth First Search

I don’t know

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

2027. Minimum Moves to Convert String

Problem Description

Intuition

Solution Approach

Example Walkthrough

Solution Implementation

Time and Space Complexity

Time Complexity

Space Complexity

Recommended Readings