• This article has participated in the “Digitalstar Project” and won a creative gift package to challenge the creative incentive money.

Thank you very much for reading this article. Welcome [👍 like] [⭐ collect] [📝 comment] ~ Give up is not difficult, But insists it must be very cool ~ hope we all can be a little bit of progress every day ~ in this paper, from two headed white hat original ~ https://juejin.cn/user/2771185768884824/posts blog

1221. Split balance string:

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, and the split balanced string is a continuous substring of the original balanced string.

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

Sample 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

The sample 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

Sample 3

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

The sample of 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

prompt

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

Analysis of the

  • This algorithm is a little bit harder if s itself is not a balanced string.
  • Since S is itself a balanced string, greedy can be used from left to right, the shorter you are, the more you can divide, and the rest of the string is also a balanced string.
  • We need to keep track of the number of ‘L’ and ‘R’ in the loop, and if they are equal, it’s a balanced string.
  • It takes two variables to record the number of ‘L’ and ‘R’, but we can record the difference between them. If the difference is 0, the number is equal, which is the balance string, and only one variable is needed to record it.

Answer key

java

class Solution {
    public int balancedStringSplit(String s) {
        int ans = 0;
        // Record the difference between left and right, subtract left, add right, 0 means left and right are the same amount
        int v = 0;
        int n = s.length();
        for (int i = 0; i < n; ++i) {
            if (s.charAt(i) == 'L') {
                --v;
            } else {
                ++v;
            }
            if (v == 0) { ++ans; }}returnans; }}Copy the code

c

int balancedStringSplit(char * s){
    int ans = 0;
    // Record the difference between left and right, subtract left, add right, 0 means left and right are the same amount
    int v = 0;
    while (*s) {
        *s == 'L' ? --v : ++v;
        if (v == 0) {
            ++ans;
        }
        ++s;
    }
    return ans;
}
Copy the code

c++

class Solution {
public:
    int balancedStringSplit(string s) {
        int ans = 0;
        // Record the difference between left and right, subtract left, add right, 0 means left and right are the same amount
        int v = 0;
        for (char c : s) {
            c == 'L' ? --v : ++v;
            if (v == 0) { ++ans; }}returnans; }};Copy the code

python

class Solution:
    def balancedStringSplit(self, s: str) - >int:
        ans = 0
        # record the difference between left and right, subtract left, add right, 0 means left and right are the same amount
        v = 0
        for c in s:
            if c == 'L':
                v -= 1
            else:
                v += 1
            if v == 0:
                ans += 1
        return ans
Copy the code

go

func balancedStringSplit(s string) int {
    ans := 0
	// Record the difference between left and right, subtract left, add right, 0 means left and right are the same amount
	v := 0
	for _, c := range s {
		if c == 'L' {
			v--
		} else {
			v++
		}
		if v == 0 {
			ans++
		}
	}
	return ans
}
Copy the code

rust

impl Solution {
    pub fn balanced_string_split(s: String) - >i32 {
        s.chars().scan(0, |v, c| {
            match c {
                'L' => *v -= 1,
                _ => *v += 1
            };
            Some(*v)
        }).filter(|v| { *v == 0 }).count() as i32}}Copy the code

Portal: https://leetcode-cn.com/problems/split-a-string-in-balanced-strings/

Please feel free to discuss in the comments section. The nuggets will draw 100 nuggets in the comments section after the diggnation project. See the event article for details