algoadvance

Leetcode 1221. Split a String in Balanced Strings

Problem Statement

Leetcode Problem 1221: Split a String in Balanced Strings

You are given a string s of ‘L’ and ‘R’ characters, and you need to split this string into as many balanced strings as possible.

A balanced string is defined as a string with an equal number of ‘L’ and ‘R’ characters.

Return the maximum number of balanced strings you can obtain.

Clarifying Questions

  1. Input Constraints:
    • Is the length of the string constrained (e.g., maximum length)?
    • Are there any constraints regarding the characters in the string (will it always contain only ‘L’ and ‘R’)?
  2. Output
    • What should be returned if the input string cannot be split into any balanced strings? (This might be inherently handled by the problem constraints).

Strategy

To solve this problem, we can use a greedy approach where we count ‘L’ and ‘R’ characters as we traverse the string:

  1. Initialize a counter (let’s call it balance) and another counter for the number of balanced strings (num_balanced).
  2. Traverse the string character by character:
    • Increment balance by 1 for ‘L’ and decrement it by 1 for ‘R’.
    • Whenever balance becomes zero, it means we have found a balanced string.
  3. Count each instance where balance becomes zero, as it indicates a balanced substring.

Code

#include <iostream>
#include <string>

int balancedStringSplit(std::string s) {
    int balance = 0;
    int num_balanced = 0;
    
    for (char c : s) {
        if (c == 'L') {
            balance++;
        } else if (c == 'R') {
            balance--;
        }
        
        if (balance == 0) {
            num_balanced++;
        }
    }
    
    return num_balanced;
}

int main() {
    std::string s = "RLRRLLRLRL";
    std::cout << balancedStringSplit(s) << std::endl;  // Output: 4
    
    return 0;
}

Time Complexity

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI