Leetcode problem 79 - Split a String in Balanced Strings

Balanced strings are those that have an equal quantity of ‘L’ and ‘R’ characters.

Given a balanced string s, split it into some number of substrings such that:

Each substring is balanced. 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 same number of ‘L’ and ‘R’. Example 2:

Input: s = “RLRRRLLRLL” Output: 2 Explanation: s can be split into “RL”, “RRRLLRLL”, each substring contains same number of ‘L’ and ‘R’. Note that s cannot be split into “RL”, “RR”, “RL”, “LR”, “LL”, because the 2nd and 5th substrings are not balanced. Example 3:

Input: s = “LLLLRRRR” Output: 1 Explanation: s can be split into “LLLLRRRR”.

Constraints:

2 <= s.length <= 1000 s[i] is either ‘L’ or ‘R’. s is a balanced string.

/**
 * @param {string} s
 * @return {number}
 */
var balancedStringSplit = function (s) {
  // Initialize variables 'balance' to track the current balance of 'L' and 'R' characters, and 'matches' to count the number of balanced substrings.
  let balance = 0,
    matches = 0;

  // Iterate through each character in the input string.
  for (let i = 0; i < s.length; i++) {
    // Update the 'balance' based on the current character ('R' decreases balance, 'L' increases balance).
    if (s[i] === "R") {
      balance -= 1;
    } else if (s[i] === "L") {
      balance += 1;
    }

    // Check if the current balance is zero, indicating a balanced substring, and increment the 'matches' count.
    if (balance === 0) {
      matches += 1;
    }
  }
  // Return the final count of balanced substrings.
  return matches;
};

Initializes two variables, balance and matches, to keep track of the balance of ‘L’ and ‘R’ characters and the count of balanced substrings, respectively.

Iterates through each character of the input string ‘s’.

Checks the current character and updates the balance accordingly (‘R’ decreases, ‘L’ increases).

Checks if the balance is zero, indicating a balanced substring, and increments the ‘matches’ count.

Returns the final count of balanced substrings.

The time complexity of the function is O(n) due to the linear iteration through the input string, making it an efficient solution for counting balanced substrings.