Using the same structure as a bubblesort algorithm

Solution to this problem resembles the same structure as a bubble-sort algorithm, which would be:

done = false

while(not done)

  done = true

  try to swap at least one pair. if success, done = false

It is an N^2 solution, for the problem below with N=1000, it works very quickly. Problem and solution down below, cheers, ACC.

Minimum Moves to Convert String - LeetCode

2027. Minimum Moves to Convert String

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
We select all the 3 characters and convert them in one move.

Example 2:

Input: s = "XXOX"
Output: 2
Explanation: XXOX -> OOOX -> OOOO
We select the first 3 characters in the first move, and convert them to 'O'.
Then we select the last 3 characters and convert them so that the final string contains all 'O's.

Example 3:

Input: s = "OOOO"
Output: 0
Explanation: There are no 'X's in s to convert.

 

Constraints:

• 3 <= s.length <= 1000
• s[i] is either 'X' or 'O'.

Accepted

7,165

Submissions

14,440

public int MinimumMoves(string s)
{
    StringBuilder sb = new StringBuilder(s);

    int count = 0;
    bool done = false;
    while (!done)
    {
        done = true;
        for (int i = 0; i < sb.Length; i++)
        {
            if (sb[i] == 'X')
            {
                for (int j = 0; j < 3; j++)
                {
                    if (i + j < sb.Length)
                    {
                        sb[i + j] = 'O';
                    }
                }
                count++;
                done = false;
            }
        }
    }

    return count;
}