Split a String in Balanced Strings

Easy
239.

Split a String in Balanced Strings

Split a String in Balanced Strings is an easy coding problem on strings, greedy and counting, asked in Amazon and Adobe interviews.

A string is balanced when it contains an equal number of 'L' and 'R' characters.

Given a balanced string s, split it into the maximum number of balanced substrings and return that count.

Example 1

Input
s = "RLRRLLRLRL"
Output
4
Explanation
The pieces are "RL", "RRLL", "RL" and "RL".

Example 2

Input
s = "RLRRRLLRLL"
Output
2

Example 3

Input
s = "LLLLRRRR"
Output
1

Constraints

  • 2 <= s.length <= 40
  • s[i] is 'L' or 'R'.
  • s is balanced.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @return {number}
 */
var balancedStringSplit = function(s) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Split a String in Balanced Strings — Problem & Solution

Split a String in Balanced Strings solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Split a String in Balanced Strings is an easy coding problem on strings, greedy and counting, asked in Amazon and Adobe interviews.

  • Difficulty: Easy
  • Topics: Strings, Greedy, Counting
  • Asked at: Amazon, Adobe
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

A string is balanced when it contains an equal number of 'L' and 'R' characters.

Given a balanced string s, split it into the maximum number of balanced substrings and return that count.

Example 1

Input: s = "RLRRLLRLRL"
Output: 4
Explanation: The pieces are "RL", "RRLL", "RL" and "RL".

Example 2

Input: s = "RLRRRLLRLL"
Output: 2

Example 3

Input: s = "LLLLRRRR"
Output: 1

Constraints

  • 2 <= s.length <= 40
  • s[i] is 'L' or 'R'.
  • s is balanced.

Hints for Split a String in Balanced Strings

  1. Hint 1

    Track a running balance: +1 for R, -1 for L.

  2. Hint 2

    Every time the balance returns to zero, you have completed a balanced piece — cut there.

  3. Hint 3

    Cutting at the earliest opportunity is what maximises the count.

How to solve Split a String in Balanced Strings

Keep a running balance (+1 for R, -1 for L) and cut every time it returns to zero.

Approach

  1. Set balance = count = 0.
  2. For each character, adjust balance; when it hits 0, increment count.
  3. Return count.

Why it works

Each return to zero closes a balanced piece, and cutting at the earliest opportunity never prevents later cuts — any balanced string splits into the pieces between successive zero crossings, which is the maximum.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • Greedy is exact here because the whole string is guaranteed balanced.

Reference solution

Python

def balancedStringSplit(s: str) -> int:
    balance = count = 0
    for ch in s:
        balance += 1 if ch == "R" else -1
        if balance == 0:
            count += 1
    return count

Java

public static int balancedStringSplit(String s) {
    int balance = 0, count = 0;
    for (int i = 0; i < s.length(); i++) {
        balance += s.charAt(i) == 'R' ? 1 : -1;
        if (balance == 0) count++;
    }
    return count;
}

C++

int balancedStringSplit(string s) {
    int balance = 0, count = 0;
    for (char c : s) {
        balance += c == 'R' ? 1 : -1;
        if (balance == 0) count++;
    }
    return count;
}

JavaScript

var balancedStringSplit = function(s) {
    let balance = 0, count = 0;
    for (let i = 0; i < s.length; i++) {
        balance += s[i] === "R" ? 1 : -1;
        if (balance === 0) count++;
    }
    return count;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Greedy Algorithms