algoadvance

You are given a string s consisting of lowercase English letters. A move consists of choosing any 3 consecutive characters of s and converting them to 'XXX'. Note that the characters in the string do not necessarily need to be distinct. Return the minimum number of moves required so that all the characters of s are converted to 'X'.

Example:

1. Input: s = "XXX", Output: 0
2. Input: s = "XXXT", Output: 1
3. Input: s = "TXXTXX", Output: 2

Clarifying Questions

1. Does the transformation of characters in the move only care about converting the characters, or do we have to concern ourselves with their original values?
   • Only concerned with converting to 'X'.
2. Do overlapping groups of three consecutive characters count as separate moves?
   • No, each move consists of exactly three consecutive characters, ensuring no overlap.

Strategy

1. Iterate through the string checking sequences of three consecutive characters.
2. Whenever a sequence that includes any non-‘X’ character is found, increment a move counter and convert that sequence in the string to 'XXX'.
3. Continue traversing the string by skipping 3 indices ahead whenever you make a move, as the conversion affects that segment.

Code

def minimumMoves(s: str) -> int:
    moves = 0
    i = 0
    while i < len(s):
        if s[i] != 'X':
            moves += 1
            i += 3  # Skip the next 3 characters because they will be converted to 'XXX'
        else:
            i += 1  # Move to the next character to check for non-'X'
    return moves

# Example Usage
print(minimumMoves("XXX"))      # Output: 0
print(minimumMoves("XXXT"))     # Output: 1
print(minimumMoves("TXXTXX"))   # Output: 2

Time Complexity

• Time complexity: O(n), where n is the length of the string s. We traverse each character in the string once, skipping ahead by 3 indices whenever a move is made.
• Space complexity: O(1), no extra space other than a few pointers and counters is used.

This strategy ensures we efficiently count the minimum number of moves needed to convert the string.

Try our interview co-pilot at AlgoAdvance.com

• 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?