Pankaj Tanwar
Published on

Minimum Moves to Convert String.

––– views

Hey-yo!

This is edition #27 of my coding diary where I take a daily coding challenge and share my thought process with some interesting ways to solve the problem.

Let's directly jump to the problem and see what we have for today!

Problem of the day - Minimum Moves to Convert String

Tag - Easy

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

The problem statement might give a feel of some sort of the dynamic programming but it's not! It can be easily solved with the greedy approach itself.

After careful observation, we can see that whenever we encounter an X, we can make a move (convert the next 3 elements to O) without caring what the next elements are. Then, we move out pointer to 3 steps because we have already taken the step to covert all X (if any) to O.

I guess, from the code, you will be able to understand it better.

Solution

class Solution {
public:
    int minimumMoves(string s) {
        int res = 0;
        for(int i=0;i<s.length();i++) {
			// whenever we see X
            if(s[i] == 'X') {
				// make a move by assuming converted all 3 char to 'O'
                res++;
                i += 2;
            }
        }
        return res;
    }
};

Pretty easy-peasy! I was able to come up with the solution in one go only.

Complexity

Time - O(n) [we iterated over the complete string of length] Space - O(1) [No extra space was used]

That was a good problem, teaching us not to complicate our algorithm every time. The greedy approach might help us in such a situation.

I welcome your suggestions!

Thanks for being part of my daily-code-workout journey. As always, if you have any thoughts about anything shared above, don't hesitate to reach out.

You might like previous editions of my coding diary

Tweet this article