This is the question of the day for 2021-9-7 in LeetCode: “1221. Split Balanced Strings”

1. Topic description

In a balanced string, the number of ‘L’ and ‘R’ characters is the same.

You are given a balanced string s and please split it into as many balanced strings as possible.

Note: Each split string must be a balanced string.

Returns the maximum number of balanced strings that can be split.

Example 1:

Input: s = "RLRRLLRLRL" Output: 4 Explanation: S can be split into "RL", "RRLL", "RL", "RL", "RL", each substring contains the same number of 'L' and 'R'.Copy the code

Example 2:

Input: s = "RLLLLRRRLR" Output: 3 Explanation: S can be split into "RL", "LLLRRR", "LR", each substring contains the same number of 'L' and 'R'.Copy the code

2. Answer

Greedy thought: to maximize the number of balanced strings, if you find one that is the shortest and satisfies the condition, divide it and continue to traverse the rest of the string.

1. Compare the number of L and R

  1. Traversal string
  2. To compareLandRThe number of
  3. ifLThe number isRAnd is not to0, then an equilibrium string is found and added to the total.
  4. LandRZero. Keep looking
const balancedStringSplit = s= > {
    let res = 0;
    let [numL, numR] = [0.0];
    const len = s.length;
    for (let i = 0; i < len; i++) {
        if (s[i] === 'L') {
            numL++;
        } else {
            numR++;
        }
        if (numL && numL === numR) {
            res++;
            numL = 0;
            numR = 0; }}return res;
};
Copy the code

2. Simplified version

  1. With a variabledTo calculateLandRThe difference between the
  2. ifdfor0On the other hand, indicateLandRIf the number is equal, an equilibrium string is found and added to the total
  3. Continue to look for
const balancedStringSplit = s= > {
    let [res, d] = [0.0];
    const len = s.length;
    for (let i = 0; i < len; i++) {
        d = s[i] === 'L' ? d + 1 : d - 1; ! d && res++; }return res;
};
Copy the code

😄 has recently created an open source repository to summarize LeetCode’s daily problems. It is currently available in C++ and JavaScript, and you are welcome to provide other language versions!

🖥️ Warehouse address: “One of the Day series”