algoadvance

Leetcode 2027. Minimum Moves to Convert String

Problem Statement

You are given a string s consisting of n characters where each character is either 'X' or '.'. A move consists of changing three consecutive characters from 'X' to '.'. Your task is to return the minimum number of moves required to convert the string such that there are no characters 'X' in the string.

Clarifying Questions

Before diving into the solution, let’s clarify a few points:

1. Input Constraints: What is the maximum length of the string s?
2. Contiguous 'X': Are the 'X' characters always contiguous or can they be scattered throughout the string?
3. Edge Cases: What should we return if the string is already composed entirely of '.'?
4. Changes to Non-contiguous 'X': Can the moves overlap? Would changing three Xs affect adjacent characters?

We will assume:

• The string s can be of any length up to a reasonably large constraint.
• 'X' characters can appear anywhere intermittently and the moves do not overlap; each move affects a distinct set of 3 characters.

Strategy

• We will iterate through the string from left to right.
• Whenever we encounter an 'X', we will make a move that changes the current and the next two characters to '.'.
• We will then skip the next two characters as they have been taken care of by the current move.
• Repeat until we reach the end of the string.

Code

Here is the C++ code to solve the problem:

#include <iostream>
#include <string>

int minimumMoves(std::string s) {
    int n = s.size();
    int moves = 0;

    for (int i = 0; i < n; ++i) {
        if (s[i] == 'X') {
            // We found an 'X', hence we make a move to turn this and next two characters into '.'
            moves++;
            // Skip the next two characters since this move will already convert them
            i += 2;
        }
    }

    return moves;
}

int main() {
    std::string s = "XX.XX..XXX";
    std::cout << "Minimum moves to convert the string: " << minimumMoves(s) << std::endl;
    return 0;
}

Explanation

1. Initialization: Start with moves = 0 and iterate through each character of s.
2. Handling ‘X’:
   • If we encounter an ‘X’, increment the moves counter.
   • Skip the next two characters since they are also converted to '.' by this move.
3. Iteration: Continue till the end of the string.
4. Returning Result: The moves variable will contain the minimal number of moves required.

Time Complexity

• Time Complexity: O(n), where n is the length of the string. This is because we iterate through the string once.
• Space Complexity: O(1), as we are using only a few extra variables and the space required does not depend on the input size.

This approach ensures that we efficiently find the minimal number of moves required to convert all 'X' characters in the string to '.'.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?