1234. Replace the Substring for Balanced String - start from contest

Here is my post.

It is one of medium algorithm in weekly contest. I spent one hour to work on the algorithm, and I could not make it work since I came cross the failed test case. I spent another 14 minutes after the contest and my code worked.

Case study

I like to list a few test cases I failed, and then I had to work on my understanding, or my design.

1. "WWEQERQWQWWRWWERQWEQ" should return 4, my return is 3. I noticed that I need to run a sliding window to count substring containing all necessary chars;
2. "QWER" return 0, my code returns 1. So I added statement to return 0 if sum = 0;
3. "WQWRQQQW", return should be 3, my code returns 5; so I added the design to allow count[] be negative value.

Here are highlights:

1. Understand how to map "QWER" to index position using String.IndexOf
2. Use two things to track sliding window, total char needs to be replaced (only count chars bigger than average), and also count array to record detail of char count;
3. Sliding window - make sure that each char only counts once - hashset is added
4. Sliding winodw - left, index define the window start and end pointer. Make it work first, later need to refine.

public class Solution {
    public int BalancedString(string s) {
        var length = s.Length;
            // QWER
            var count = new int[4];
            for (int i = 0; i < length; i++)
            {
                var current = s[i];
                if (current == 'Q')
                    count[0]++;
                if (current == 'W')
                    count[1]++;
                if (current == 'E')
                    count[2]++;
                if (current == 'R')
                    count[3]++;
            }

            int sum = 0;
            for (int i = 0; i < 4; i++)
            {
                count[i] -= length / 4;
                if (count[i] < 0)
                    count[i] = 0;

                sum += count[i];
            }
        
            if (sum == 0)
                return 0; 


            return findMinimumSubstring(s, sum, count);            
        }

        private static int findMinimumSubstring(string s, int sum ,int[] count)
        {
            var countCopy = new int[4];
            for (int i = 0; i < 4; i++)
                countCopy[i] = count[i];

            var minLength = s.Length;
            var left = 0;
            var index = 0;
            var length = s.Length; 
            var marks = "QWER";
            var rightCount = new HashSet<int>(); 

            // QWER  WWEQERQWQWWRWWERQWEQ
            while(index < length)
            {
                var current = s[index];
                var countIndex = marks.IndexOf(current);

                if (!rightCount.Contains(index))
                {
                    if (count[countIndex] > 0)
                    {
                        sum--;
                    }
                    count[countIndex]--;                    
                }

                rightCount.Add(index); 

                if(sum == 0 && left <= index)
                {
                    var window = index - left + 1;
                    minLength = window < minLength ? window : minLength;
                    
                    // move left pointer
                    var remove = s[left];
                    var removeIndex = marks.IndexOf(remove);
                    if(countCopy[removeIndex] > 0)
                    {                        
                        count[removeIndex]++;
                        if (count[removeIndex] > 0)
                            sum++;
                    }

                    left++; 
                }
                else
                {
                    index++; 
                }                
            }

            return minLength;
        }
}