algoadvance

Leetcode 2027. Minimum Moves to Convert String

Problem Statement

You are given a string s consisting of lowercase English letters. You are allowed to convert any segment of 3 consecutive characters ‘x’ to ‘O’. You need to return the minimum number of moves required to convert all the ‘x’ characters in the string to ‘O’.

• For example, if s = "xxoxxox", you can convert the first 3 characters (“xxo”) and the last 3 characters (“xox”) independently, resulting in “OooOooox”.

Clarifying Questions

1. Q: Can segments overlap when converting ‘x’ to ‘O’? A: No, segments can’t overlap. Each segment of 3 consecutive ‘x’s should be independent and non-overlapping.

2. Q: Do we need to handle any uppercase characters or non-alphabetic characters? A: No, the problem guarantees that the string consists of lowercase English letters only.

3. Q: What is the expected length range of the input string s? A: Assuming typical LeetCode constraints, length of s is from 1 to (10^5).

Strategy

1. Traverse the string s while maintaining a current index i.
2. Whenever an ‘x’ is found at the current index i, increase the counter for moves and skip the next 3 characters (i.e., set i to i + 3).
3. If the current index is not ‘x’, simply move to the next character (i.e., increment i by 1).

Code

public class Solution {
    public int minimumMoves(String s) {
        int moves = 0;
        int i = 0;
        
        while (i < s.length()) {
            if (s.charAt(i) == 'x') {
                moves++;
                i += 3;
            } else {
                i++;
            }
        }
        
        return moves;
    }
    
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.minimumMoves("xxoxxox")); // Output: 3
        System.out.println(sol.minimumMoves("oxxxxo"));  // Output: 2
        System.out.println(sol.minimumMoves("ooo"));     // Output: 0
        System.out.println(sol.minimumMoves("xxxxx"));   // Output: 2
    }
}

Time Complexity

• The algorithm traverses the string s exactly once, so the time complexity is O(n) where n is the length of the string.
• This ensures efficient processing even for the upper constraint limit of 10^5 characters.

Feel free to test the implementation with different test cases or edge cases to ensure it covers all scenarios.

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?