Leetcode -1221- Split balance string

[Blog link]

The path to learning at 🐔

The nuggets home page

[答 案]

Topic link

[making address]

Making the address

[B].

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

Example 3:

Input: s = "LLLLRRRR" Output: 1 Description: S can only be "LLLLRRRR".Copy the code

Example 4:

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

Tip:

  • 1 <= s.length <= 1000
  • S [I] = ‘L’ or ‘R’
  • S is an equilibrium string

Idea 1: Greedy method

  • The proof of greedy law proves by induction, the solution of three leaf big guy is very good everybody can go to see!
  • I’m not going to repeat it here
public int balancedStringSplit(String s) {
    //corner case
    if (s.length() == 1) {
        return 1;
    }
    int temp = s.charAt(0) = ='R' ? 1 : -1, res = 0;
    for (int i = 1; i < s.length(); i++) {
        if (s.charAt(i) == 'R') temp++;
        else temp--;
        if (temp == 0){ res++; }}return res;
}
Copy the code
  • Time complexity O(n)
  • Space complexity O(1)