leetcode1221. Split balance string

LeetCode Series articles

One 、 Title Description

   In a balanced string ,${}^{\prime }{L}^{\prime }$ and ${}^{\prime }{R}^{\prime }$ The number of characters is the same .
 
   Give you a balanced string $s$, Please split it into as many balanced strings as possible .
 
   Returns the maximum number of balanced strings that can be split .
 
   Be careful ： Each split string must be a balanced string , And the balanced string obtained by segmentation is a continuous substring of the original string .

Two 、 Example

   Input ： s = “RLRRLLRLRL”
   Output ： 4
 
   explain ： s Can be divided into “RL”、“RRLL”、“RL”、“RL”, Each substring contains the same number of ‘L’ and ‘R’ .

3、 ... and 、 Main idea

   This topic actually investigates the greedy algorithm , That is, when solving problems , Always make what seems to be the best choice at the moment . For this topic , When we iterate over the balanced string for segmentation , Once a sub balanced string is found, it should be split immediately .
 
   For example, for balanced strings “RLRRLLRLRL”, We can traverse to “RL” Split it up , You can also traverse to “RLRRLL” Then split it , because “RL” and “RLRRLL” Are balanced strings .

   But the question requires the maximum number of balanced strings obtained by segmentation , So we are traversing to “RL” Should be split , At this time, the following “RRLL” Can be split into another balanced string . Follow this method to traverse the given balanced string , Finally, the maximum number of balanced strings that can be obtained after segmentation .
 
   It should be noted that , The given balance string must eventually be divided into several complete sub balance strings , There will be no case that some of the remaining characters cannot form a balanced string . Because when you separate a sub balanced string from the balanced string , Among the remaining strings R and L The number of must be equal , So this string is also a balanced string .
 
As shown in the figure below ：

Four 、 Code implementation

When analyzing the problem, the split string is just for convenience , In fact, there is no need to segment the string when solving the problem .

• We can define one level Variable , The initial value of this variable is set to 0.
• In the process of balancing strings with variables , If the traversed character is R, On the other hand level Since it increases , If the traversed character is L, On the other hand level Since the subtract .（ And vice versa ）
• except level Setting of initial value , In the process of traversing level The value of has changed to several times 0, It indicates the maximum number of sub balance strings that the balance string can be divided into .

 
Dynamic diagram demonstration ：

The code is as follows ：