# 1221. Split a String in Balanced Strings

LeetCode Problem Link (opens new window)

In a balanced string, the number of 'L' and 'R' characters are equal.

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

Note: Every substring obtained after splitting should be a balanced string.

Return the maximum number of balanced strings you can obtain.

Example 1:

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

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'.

Example 3:

Input: s = "LLLLRRRR"
Output: 1
Explanation: s can only be kept as "LLLLRRRR".

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'.

# Approach

At first glance, this problem seems complex, but it is, in fact, a very simple greedy algorithm. Regarding greedy algorithms, I have explained them in detail here (opens new window).

Traverse from the front to the end. Whenever you encounter a balanced substring, increase the count by 1. Go through the string once to get the result.

Local optimal: Traverse, and whenever a balanced substring is found, record it.

Global optimal: Record the maximum number of balanced substrings.

Given that the local optimal can lead to the global optimal without counterexamples, we can try this greedy approach.

For example, "LRLR" is already a balanced substring, but splitting on "LR" can be more advantageous.

C++ code below:

class Solution {
public:
    int balancedStringSplit(string s) {
        int result = 0;
        int count = 0;
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == 'R') count++;
            else count--;
            if (count == 0) result++;
        }
        return result;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13

# Extension

Some might wonder about the reliability of this reasoning as there's no mathematical proof. How can we say the local optimal can lead to the global optimal?

Generally, mathematical proofs can be done via the following methods:

Mathematical induction
Proof by contradiction

If we were to strictly prove it mathematically, it is not within the scope of these coding problems or interviews.

Thus, the thought process for greedy algorithms is: if the local optimal seems to lead to the global optimal, attempt to provide a counterexample. If no counterexample can be made, then try the greedy approach.

# Other Language Versions

# Java

class Solution {
    public int balancedStringSplit(String s) {
        int result = 0;
        int count = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == 'R') count++;
            else count--;
            if (count == 0) result++;
        }
        return result;
    }  
}

1
2
3
4
5
6
7
8
9
10
11
12

# Python

class Solution:
    def balancedStringSplit(self, s: str) -> int:
        diff = 0  # Difference between 'R' and 'L'
        ans = 0
        for c in s:
            if c == "L":
                diff -= 1
            else:
                diff += 1
            if diff == 0:
                ans += 1
        return ans

1
2
3
4
5
6
7
8
9
10
11
12

# Go

func balancedStringSplit(s string) int {
    diff := 0 // Difference between 'R' and 'L'
    ans := 0
    for _, c := range s {
        if c == 'L' {
            diff--
        } else {
            diff++
        }
        if diff == 0 {
            ans++
        }
    }
    return ans
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# JavaScript

var balancedStringSplit = function(s) {
    let res = 0, total = 0; // res is the number of balanced strings, total is the current difference between 'R' and 'L'
    for(let c of s){ // Traverse through each character in the string
        // Adjust the total before checking if it's zero
        total += c === 'R' ? 1 : -1; // Increase for 'R', decrease for 'L'
        if(total === 0) res++; // If 'R' and 'L' counts are equal, increase the count
    }
    return res;
};

1
2
3
4
5
6
7
8
9

# TypeScript

function balancedStringSplit(s: string): number {
    let count: number = 0
    let res: number = 0
    for(let i of s){
        if(i === 'R') count++
        else count--
        if(count === 0) res++
    }

    return res
};

1
2
3
4
5
6
7
8
9
10
11