1234. Replace the Substring for Balanced String - Top players

Oct. 20, 2019

Introduction

I am lack of strong motivation in weekdays, but I do learn from my Saturday 7:30 pm 90 minutes weekly contest very well. Starting from 7:30 PM, I had four hour activities including contest, review, writing and exchange ideas.

Case study

Here are some facts:
1. One hour to work on algorithm 1234, another 15 minutes after the contest to complete the code;
2. Learned one more solution;
3. Studied top player ranking No. 1.

From 7:30 PM to 11:30 PM, that is four hours learning.

I have difficulty to describe using my English. There are some structure issues:

One hour struggle on this medium level algorithm 1234, I spent another 15 minutes after the contest to complete the code, and then learned one more algorithm, studied top player ranking No. 1. From 7:30 PM to 11:30 PM, that is four hours learning.

Here is the post.

C# code study: Weekly contest 159 ranking No. 1 - binary search

It is interesting to learn a solution written by weekly contest 159 ranking No. 1. Since his solution was written in less than 4 minutes. I like to figure out how we can shorten the time and expedite the problem solving process.

I will add more understanding how to design and make the code easy and quick to write. I think that as a designer, I have to learn various ideas to solve the problems first, and then I can choose easy one to write in weekly contest.

public class Solution {
    public int BalancedString(string s) {
         const string CHARS = "QWER";
            int length = s.Length; 
            var prefixCounts = new int[4][];

            for(int i = 0; i < 4; i++)
            {
                prefixCounts[i] = new int[length + 1]; 

                for(int j = 0; j < length; j++ )
                {
                    prefixCounts[i][j + 1] = prefixCounts[i][j] + (s[j] == CHARS[i]? 1 : 0); 
                }
            }

            int low = 0;
            int high = length; 

            while(low < high)
            {
                int middle = low + (high - low)/ 2; 
                var seriesCheck = false;

                for(int i = 0; i + middle <= length; i++)
                {
                    var now = new int[4];
                    var averageCheck = true; 

                    for(int j = 0; j < 4; j++)
                    {
                        now[j] = prefixCounts[j][i] + (prefixCounts[j][length] - prefixCounts[j][i + middle]);

                        if(now[j] > length/ 4)
                        {
                            averageCheck = false; 
                        }
                    }

                    seriesCheck = seriesCheck || averageCheck;
                }     
           
                if(seriesCheck)
                {
                    high = middle; 
                }
                else
                {
                    low = middle + 1; 
                }
            }

            return low; 
    }
}