2027. Minimum Moves to Convert String
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.
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 to0
andi
which is our pointer to iterate through the string, initially set to0
. -
We use a
while
loop to iterate over the string untili
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 theans
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 pointeri
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.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample 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 changes[0:3]
from'XXO'
to'OOO'
. We increment our answer to1
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 ons[4:7]
, changing'OOX'
to'OOO'
. We increment our answer to2
and skip 3 characters to index 7. -
At position 7, we find another
'X'
. We perform the operation ons[7:10]
, changing'XOX'
to'OOO'
. Increment our answer to3
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 ons[10:13]
(which is actually just up tos[11]
since we've reached the end), changing'OX'
to'OO'
. We increment our answer to4
.
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
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.
Which of the following array represent a max heap?
Recommended Readings
Greedy Introduction div class responsive iframe iframe src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe div When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you to calculate the max min of some value Commonly you may see this phrased in the problem as max min longest shortest largest smallest etc These keywords can be identified by just scanning
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first