Jobs

Interviews

Discussions

Minimum Moves to Convert String

Easy

Asked by:

13 views

Topics:

StringsGreedy Algorithms

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

Example 1:

Input: s = "XXX"
Output: 1
Explanation: XXX -> OOO
We select all the 3 characters and convert them in one move.

Example 2:

Input: s = "XXOX"
Output: 2
Explanation: XXOX -> OOOX -> OOOO
We select the first 3 characters in the first move, and convert them to 'O'.
Then we select the last 3 characters and convert them so that the final string contains all 'O's.

Example 3:

Input: s = "OOOO"
Output: 0
Explanation: There are no 'X's in s to convert.

Constraints:

3 <= s.length <= 1000
s[i] is either 'X' or 'O'.

Try coding it in LeetCode

Minimum Moves to Convert String

Easy

Asked by:

13 views

Topics:

StringsGreedy Algorithms

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

Example 1:

Input: s = "XXX"
Output: 1
Explanation: XXX -> OOO
We select all the 3 characters and convert them in one move.

Example 2:

Input: s = "XXOX"
Output: 2
Explanation: XXOX -> OOOX -> OOOO
We select the first 3 characters in the first move, and convert them to 'O'.
Then we select the last 3 characters and convert them so that the final string contains all 'O's.

Example 3:

Input: s = "OOOO"
Output: 0
Explanation: There are no 'X's in s to convert.

Constraints:

3 <= s.length <= 1000
s[i] is either 'X' or 'O'.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What characters can the input string `s` contain, and are there any constraints on its length?
If the string is already composed only of 'O's, should I return 0?
Is the target 'X' substring always of length 3, or could the target length be different?
If I reach the end of the string and a partial substring of 'X's exists that isn't fully covered by a move, do I still need to make a move to cover it?
Are there any edge cases where the input string `s` might be null or empty?

Brute Force Solution

Approach

The brute force method for this problem involves systematically testing every possible move sequence to transform the string. We explore all combinations of covering characters until we find one that converts the entire string with the fewest moves. It's like trying every single thing you can do until something works.

Here's how the algorithm would work step-by-step:

Start at the beginning of the string.
Consider covering only the first character with a move.
Then, try covering the first two characters with a move.
Continue this, trying to cover the first three characters with a move.
For each of these 'first moves', look at the remaining uncovered characters.
For the remaining characters, repeat the process: try covering the next character, then the next two, then the next three.
Keep doing this until the entire string is covered in 'moves'.
Count how many 'moves' each combination needed.
After exploring all possible combinations of moves, pick the combination that used the fewest 'moves' to cover the entire string. That is the answer.

Code Implementation

def minimum_moves_to_convert_string_brute_force(input_string):
    minimum_number_of_moves = float('inf')

    def solve(current_index, number_of_moves):
        nonlocal minimum_number_of_moves

        # If we've reached the end of the string, update min moves.
        if current_index >= len(input_string):
            minimum_number_of_moves = min(
                minimum_number_of_moves, number_of_moves
            )
            return

        # If current character needs no conversion, skip it.
        if input_string[current_index] == 'O':
            solve(current_index + 1, number_of_moves)
            return

        # Try covering 1, 2, or 3 characters starting at current_index.
        for characters_to_cover in range(1, 4):
            # This makes sure we don't go out of bounds.
            if current_index + characters_to_cover > len(input_string):
                break

            solve(
                current_index + characters_to_cover,
                number_of_moves + 1
            )

    solve(0, 0)

    return minimum_number_of_moves

Big(O) Analysis

Time Complexity

O(3^n) – The algorithm explores all possible moves by, in essence, checking every possible subset of characters that could be covered by a move of length 3. For each character, we have a choice: either it's covered by a move starting at that character, or it's not. Since each move covers up to 3 characters, we can consider this as making a decision at each position: start a move here, or don't. Because we iterate through positions and need to check all combinations of moves which affect up to 3 characters for each position, the number of possible combinations grows exponentially with the size of the string. There are at most n/3 moves, so the number of operations will be 3 * 3 * ... * 3 = 3^(n/3), which is O(3^n) since the size of the substring is bounded by a constant, and we have to repeat this process for each of the n positions. Thus, the time complexity is O(3^n).

Space Complexity

O(N^K) – The brute force approach explores all possible combinations of moves, which can be visualized as a tree where each node represents a choice of covering 1, 2, or 3 characters. In the worst-case, the depth of this tree could be N/3 (where N is the length of the string), and at each level, we're essentially creating copies or slices of the remaining string to explore further combinations. The number of branches at each node also contributes to the space, as we are considering multiple paths at each level. Therefore, the space complexity is exponential, specifically O(3^(N/3)) which is a more precise expression. However, to account for combinations that cover fewer characters at each move, we can generalize the space complexity as O(N^K), where K is some constant based on the number of possible moves at each step (up to 3 characters covered).

Optimal Solution

Approach

The goal is to find the fewest actions needed to change a string entirely to 'O's. The clever trick is to realize that one action can cover three characters, so we want to maximize the coverage of each action by focusing on the 'X's.

Here's how the algorithm would work step-by-step:

Start at the beginning of the string.
Go through the string character by character until you find an 'X'.
When you find an 'X', perform an action to cover that 'X' and the two characters immediately after it.
Jump ahead three characters since those are now covered by the action.
Keep going through the remaining string, repeating steps two through four.
Count the total number of actions performed; this is the minimum number of moves.

Code Implementation

def minimum_moves_to_convert_string(input_string):
    string_length = len(input_string)
    moves_count = 0
    index = 0

    while index < string_length:
        if input_string[index] == 'X':
            # Found an 'X', so we need to make a move.
            moves_count += 1

            # Each move covers three characters.
            index += 3

        else:
            # Move to the next character.
            index += 1

    return moves_count

Big(O) Analysis

Time Complexity

O(n) – The solution iterates through the input string of length n at most once. The key operation is finding an 'X', and when one is found, the algorithm jumps ahead three positions. Because the jump is a constant size, the number of jumps will always be less than or equal to n/3. The number of operations is directly proportional to the length of the string n. Therefore, the time complexity is O(n).

Space Complexity

O(1) – The algorithm iterates through the input string and counts the number of actions needed. It only uses a constant number of integer variables, such as the current index and the action counter, regardless of the input string's length, N. Therefore, the auxiliary space used by the algorithm is constant. This constant space usage means the space complexity is O(1).

Edge Cases

Case	How to Handle
Null or empty string input	Return 0 immediately as no conversion is possible.
String length less than 3	If string length is less than 3 and not all characters are 'X', return 0 if all characters are 'O' else return 1 since one operation can cover up to 3 characters.
String contains characters other than 'X' and 'O'	Throw an IllegalArgumentException or return an error code, as the problem statement only defines behavior for 'X' and 'O'.
String with all 'X' characters	The minimum moves will be string length divided by 3 rounded up because each move can handle up to 3 consecutive 'X's.
String with all 'O' characters	Return 0 as no moves are needed.
String with alternating 'X' and 'O' characters (e.g., 'XOXOXOXOXO')	Each 'X' must be covered individually (or in groups of 2 or 3 with adjacent 'X's) because there are no adjacent 'X's.
Very long string exceeding memory constraints if copied	Process the string in place using a pointer to avoid unnecessary memory allocation of a new substring.
Consecutive X's at the end of the array that are fewer than 3	Handle the final 1 or 2 consecutive X's at the end correctly by counting the additional move needed.

Null or empty string input

How to Handle:

Return 0 immediately as no conversion is possible.

String length less than 3

How to Handle:

If string length is less than 3 and not all characters are 'X', return 0 if all characters are 'O' else return 1 since one operation can cover up to 3 characters.

String contains characters other than 'X' and 'O'

How to Handle:

Throw an IllegalArgumentException or return an error code, as the problem statement only defines behavior for 'X' and 'O'.

String with all 'X' characters

How to Handle:

The minimum moves will be string length divided by 3 rounded up because each move can handle up to 3 consecutive 'X's.

String with all 'O' characters

How to Handle:

Return 0 as no moves are needed.

String with alternating 'X' and 'O' characters (e.g., 'XOXOXOXOXO')

How to Handle:

Each 'X' must be covered individually (or in groups of 2 or 3 with adjacent 'X's) because there are no adjacent 'X's.

Very long string exceeding memory constraints if copied

How to Handle:

Process the string in place using a pointer to avoid unnecessary memory allocation of a new substring.

Consecutive X's at the end of the array that are fewer than 3

How to Handle:

Handle the final 1 or 2 consecutive X's at the end correctly by counting the additional move needed.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What characters can the input string `s` contain, and are there any constraints on its length?
If the string is already composed only of 'O's, should I return 0?
Is the target 'X' substring always of length 3, or could the target length be different?
If I reach the end of the string and a partial substring of 'X's exists that isn't fully covered by a move, do I still need to make a move to cover it?
Are there any edge cases where the input string `s` might be null or empty?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start at the beginning of the string.
Consider covering only the first character with a move.
Then, try covering the first two characters with a move.
Continue this, trying to cover the first three characters with a move.
For each of these 'first moves', look at the remaining uncovered characters.
For the remaining characters, repeat the process: try covering the next character, then the next two, then the next three.
Keep doing this until the entire string is covered in 'moves'.
Count how many 'moves' each combination needed.
After exploring all possible combinations of moves, pick the combination that used the fewest 'moves' to cover the entire string. That is the answer.

Code Implementation

def minimum_moves_to_convert_string_brute_force(input_string):
    minimum_number_of_moves = float('inf')

    def solve(current_index, number_of_moves):
        nonlocal minimum_number_of_moves

        # If we've reached the end of the string, update min moves.
        if current_index >= len(input_string):
            minimum_number_of_moves = min(
                minimum_number_of_moves, number_of_moves
            )
            return

        # If current character needs no conversion, skip it.
        if input_string[current_index] == 'O':
            solve(current_index + 1, number_of_moves)
            return

        # Try covering 1, 2, or 3 characters starting at current_index.
        for characters_to_cover in range(1, 4):
            # This makes sure we don't go out of bounds.
            if current_index + characters_to_cover > len(input_string):
                break

            solve(
                current_index + characters_to_cover,
                number_of_moves + 1
            )

    solve(0, 0)

    return minimum_number_of_moves

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Start at the beginning of the string.
Go through the string character by character until you find an 'X'.
When you find an 'X', perform an action to cover that 'X' and the two characters immediately after it.
Jump ahead three characters since those are now covered by the action.
Keep going through the remaining string, repeating steps two through four.
Count the total number of actions performed; this is the minimum number of moves.

Code Implementation

def minimum_moves_to_convert_string(input_string):
    string_length = len(input_string)
    moves_count = 0
    index = 0

    while index < string_length:
        if input_string[index] == 'X':
            # Found an 'X', so we need to make a move.
            moves_count += 1

            # Each move covers three characters.
            index += 3

        else:
            # Move to the next character.
            index += 1

    return moves_count

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty string input	Return 0 immediately as no conversion is possible.
String length less than 3	If string length is less than 3 and not all characters are 'X', return 0 if all characters are 'O' else return 1 since one operation can cover up to 3 characters.
String contains characters other than 'X' and 'O'	Throw an IllegalArgumentException or return an error code, as the problem statement only defines behavior for 'X' and 'O'.
String with all 'X' characters	The minimum moves will be string length divided by 3 rounded up because each move can handle up to 3 consecutive 'X's.
String with all 'O' characters	Return 0 as no moves are needed.
String with alternating 'X' and 'O' characters (e.g., 'XOXOXOXOXO')	Each 'X' must be covered individually (or in groups of 2 or 3 with adjacent 'X's) because there are no adjacent 'X's.
Very long string exceeding memory constraints if copied	Process the string in place using a pointer to avoid unnecessary memory allocation of a new substring.
Consecutive X's at the end of the array that are fewer than 3	Handle the final 1 or 2 consecutive X's at the end correctly by counting the additional move needed.

Null or empty string input

How to Handle:

Return 0 immediately as no conversion is possible.

String length less than 3

How to Handle:

If string length is less than 3 and not all characters are 'X', return 0 if all characters are 'O' else return 1 since one operation can cover up to 3 characters.

String contains characters other than 'X' and 'O'

How to Handle:

Throw an IllegalArgumentException or return an error code, as the problem statement only defines behavior for 'X' and 'O'.

String with all 'X' characters

How to Handle:

The minimum moves will be string length divided by 3 rounded up because each move can handle up to 3 consecutive 'X's.

String with all 'O' characters

How to Handle:

Return 0 as no moves are needed.

String with alternating 'X' and 'O' characters (e.g., 'XOXOXOXOXO')

How to Handle:

Each 'X' must be covered individually (or in groups of 2 or 3 with adjacent 'X's) because there are no adjacent 'X's.

Very long string exceeding memory constraints if copied

How to Handle:

Process the string in place using a pointer to avoid unnecessary memory allocation of a new substring.

Consecutive X's at the end of the array that are fewer than 3

How to Handle:

Handle the final 1 or 2 consecutive X's at the end correctly by counting the additional move needed.