Leetcode 2027: Minimum Moves to Convert String

Input: The input consists of a string `s` containing only the characters 'X' and 'O'.

Example: s = "XXOX"

Constraints:

• 3 <= s.length <= 1000

• s[i] is either 'X' or 'O'.

Output: Return the minimum number of moves required to convert all the characters of `s` to 'O'.

Example: Output: 2

Constraints:

• The result is the minimum number of operations needed.

Goal: The goal is to count how many moves are needed to convert all 'X's in the string to 'O's by selecting consecutive blocks of three characters.

Steps:

• 1. Traverse the string from left to right.

• 2. Whenever you encounter an 'X', increment the move count and skip the next two characters (as we can change three consecutive characters in one move).

• 3. Continue this process until the end of the string is reached.

Goal: Constraints for input values and operations.

Steps:

• 3 <= s.length <= 1000

• s[i] is either 'X' or 'O'.

Assumptions:

• The string `s` contains only the characters 'X' and 'O'.

• Input: s = "XXX"

• Explanation: We can convert all 'X's to 'O's in one move, resulting in 'OOO'.

• Input: s = "XXOX"

• Explanation: In the first move, we convert 'XXX' to 'OOO', yielding 'OOOX'. In the second move, we convert 'OOX' to 'OOO'.

• Input: s = "OOOO"

• Explanation: Since the string already consists of only 'O's, no moves are required.

Approach: The problem can be solved by iterating over the string and performing a move whenever an 'X' is encountered. After each move, skip the next two characters since they have been converted to 'O'.

Observations:

• The minimum number of moves corresponds to the number of non-overlapping consecutive 'X' blocks of length 3.

• A greedy approach can be applied: for each 'X' encountered, immediately make a move and move ahead by 3 characters.

Steps:

• 1. Initialize a counter for moves and a pointer to traverse the string.

• 2. Iterate through the string, and for every 'X' found, increment the counter and skip the next two characters.

• 3. Continue this until the end of the string.

Empty Inputs:

• Not applicable, as the string length is at least 3.

Large Inputs:

• Ensure that the solution runs efficiently even for the maximum input size (1000 characters).

Special Values:

• If the string contains only 'O's, no moves are needed.

Constraints:

• The approach should work within the time limits for the maximum input size.

int minimumMoves(string s) {
    int i = 0, n = s.length(), count = 0;
    while (i < n) {
        if (s[i] == 'O')
            i++;
        else
            count++, i += 3;
    }
    return count;
}

1 : Function Definition

int minimumMoves(string s) {

This defines the function 'minimumMoves' which takes a string 's' containing 'X' and 'O' and returns the minimum number of moves required to convert all 'X's to 'O's.

2 : Variable Initialization

    int i = 0, n = s.length(), count = 0;

Here, three variables are initialized: 'i' for the current index, 'n' for the length of the string, and 'count' to keep track of the number of moves.

3 : Loop Start

    while (i < n) {

This starts a while loop that iterates over the string until all characters are processed.

4 : Condition Check

        if (s[i] == 'O')

This checks if the current character is 'O'. If it is, we simply move to the next character without making any changes.

5 : Index Increment

            i++;

If the current character is 'O', we increment 'i' to move to the next character.

6 : Condition Else

        else

If the current character is 'X', we need to make a move.

7 : Move Calculation

            count++, i += 3;

In this case, we increment the move count by 1 and move the index 'i' forward by 3 to simulate changing up to three 'X's to 'O's in one move.

8 : Return Statement

    return count;

This returns the total number of moves calculated to convert all 'X's in the string to 'O's.

Best Case: O(n)

Average Case: O(n)

Worst Case: O(n)

Description: The solution involves a single traversal of the string, making it O(n) in all cases.

Best Case: O(1)

Worst Case: O(1)

Description: The space complexity is O(1) as the algorithm only requires a few variables for counting and indexing.

Leetcode 2027: Minimum Moves to Convert String

Explore →