LeetCode #1221 “Split a String in Balanced Strings”

Opening

Easy

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

Given a balanced string s split it in the maximum amount of balanced strings.

Return the maximum amount of splitted balanced strings.

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 = "RLLLLRRRLR"
Output: 3
Explanation: s can be split into "RL", "LLLRRR", "LR", each substring contains same number of 'L' and 'R'.

Example 3:

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

Example 4:

Input: s = "RLRRRLLRLL"
Output: 2
Explanation: s can be split into "RL", "RRRLLRLL", since each substring contains an equal number of 'L' and 'R'

Constraints:

  • 1 <= s.length <= 1000
  • s[i] = 'L' or 'R'

Solution

This was a tough problem for me so this writeup is more for me. First, you are already given a balanced string and a useful constraint. The useful constraint is that it is either one item or another, in this case, ‘L’ or ‘R’.

It would’ve been nice to know that anything that is balanced will always yield a 0. Whether it’s count of objects, weight between objects, leafs, etc. I had not realized that insight. For this problem, in short:

given a string, for every balanced string, increase the count by 1

There are a few ways to approach this. You’ll want to balance out a simple example first. Say your string is “RL” or “LR.”

After you loop through either string, your count should be 1. You take one object and balance against the other object. When you do this, you’re using extra space.

R_count = 0
L_count = 0
count = 0
balancing_list = 0
for letter in s:
balancing_list.append(letter)

if (balancing_list.count("L") == balancing_list.count("R")):
count += 1
balancing_list.clear()

As you can probably tell, the balancing_list variable is used as a balance. When the value of balancing_list is 0, it’s a balanced string.

If you are challenged to not use extra space, then you just have to realize another insight (I did not, under the timeframe I gave myself).

The other insight you need is tracking. That is, you’re keeping track.

tracking = 0
count = 0
for letter in s:
if letter == "L":
tracking += 1
else:
tracking -= 1
if tracking == 0:
count += 1

We are basically told that we’ll never have a lone object as that would mean there is a contradiction in the title.

Because we know that we’ll never have a lone object, we can add and subtract until we get a tracking that is equal to zero. Each iteration will involve in an operation until the end of a string.

You just need to return the final count. Thanks for reading!

--

--

--

I write just in case death knocks

Love podcasts or audiobooks? Learn on the go with our new app.

Brief Overview of Python

🔰Industry use cases of Jenkins🔰

Industry use cases of Jenkins

Those who don’t know themselves, and avoid the hard work of looking inward live life by default

Canvas WHAT? AND HOW?

Flyway in Serverless Architectures

Why are Java and C programming languages on the decline?

Deep Dive Into Preferences Datastore in Android

How to Schedule Sending an Email in Gmail

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Cassy

Cassy

I write just in case death knocks

More from Medium

Leetcode — 1 problem

LeetCode — Repeated Substring Pattern

[LeetCode][C++] #26. Remove Duplicates from Sorted Array

LeetCode Ranking 562,030 (April 28)