algoadvance

Leetcode 1221. Split a String in Balanced Strings

Problem Statement

You are given a string s of lowercase English letters. A string is called balanced if it contains an equal number of ‘L’ and ‘R’ characters.

Your task is to determine the maximum number of balanced substrings that can be obtained from the given string s. You need to return the count of these substrings.

Clarifying Questions

1. Is the input string always valid and non-empty?
   • Yes, the input string s will always be a valid and non-empty string of lowercase English letters.
2. Is the input string guaranteed to have an even length?
   • No, the input string can have both even or odd length.
3. Do we have to consider all possible substrings?
   • No, we only need to find the maximum number of balanced substrings.
4. Can substrings overlap?
   • No, once a balanced substring is created, its characters cannot be used in another substring.

Strategy

To solve the problem, you can use a counter to keep track of the balance between ‘L’ and ‘R’:

1. Initialize balance and count to 0.
2. Traverse through the string character by character.
   • Increase the balance counter by 1 for ‘L’.
   • Decrease the balance counter by 1 for ‘R’.
3. Whenever the balance is 0, it means we have found a balanced substring.
4. Increment the count of balanced substrings whenever balance is 0.
5. Return count after iterating through the string.

Code

public class Solution {
    public int balancedStringSplit(String s) {
        int balance = 0;
        int count = 0;

        for (char c : s.toCharArray()) {
            if (c == 'L') {
                balance++;
            } else {
                balance--;
            }

            if (balance == 0) {
                count++;
            }
        }

        return count;
    }
}

Time Complexity

• Time Complexity: O(n)
  • The algorithm traverses the string exactly once, where n is the length of the string s.
• Space Complexity: O(1)
  • The algorithm uses a constant amount of additional space, regardless of the input size.

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

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?