[PYTHON] Let Code Day59 starting from zero "1221. Split a String in Balanced Strings"

Overview

It seems that coding tests are conducted overseas in interviews with engineers, and in many cases, the main thing is to implement specific functions and classes according to the theme.

Apparently, many engineers take measures on the site called LetCode.

It is a site that trains the algorithmic power that can withstand the coding test that is done in the early story, and it is an inevitable path for those who want to build a career at an overseas tech company.

I wrote it in a big way, but I have no plans to have such an interview at the moment.

However, as an IT engineer, it would be better to have the same level of algorithm power as a person, so I would like to solve the problem irregularly and write down the method I thought at that time.

Leetcode

I'm solving it with Python3.

Leet Code Table of Contents Starting from Zero

Last time Leet Code Day58 starting from zero "20. Valid Parentheses"

Right now, I'm prioritizing the Medium of the Top 100 Liked Questions. I solved all Easy, so if you are interested, please go to the table of contents.

Twitter I'm doing it.

problem

1221. Split a String in Balanced Strings The difficulty level is Easy.

The problem is that the string s is given, which contains only'L' or 'R'. Divide a string with the same number of characters into the maximum amount of balanced strings and return the maximum amount of the division.

Even if you translate it yourself, it is difficult to understand, so let's see an example for the time being.

Input: s = "RLRRLLRLRL" Output: 4 Explanation: s can be split into "RL", "RRLL", "RL", "RL", each substring contains same number of 'L' and 'R'.

Input: s = "RLLLLRRRLR" Output: 3 Explanation: s can be split into "RL", "LLLRRR", "LR", each substring contains same number of 'L' and 'R'.

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

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

This is easy to understand.

solution

class Solution:
    def balancedStringSplit(self, s: str) -> int:
        count = 0
        total = 0
        for i in s:
            if i == "R":
                count += 1
            else:
                count -= 1
            if count == 0:
                total += 1
        return total
# Runtime: 28 ms, faster than 74.00% of Python3 online submissions for Split a String in Balanced Strings.
# Memory Usage: 13.9 MB, less than 40.98% of Python3 online submissions for Split a String in Balanced Strings.

Just prepare two variables and deduct them!

Thank you for the match.

That's why I brought a one-line answer from discuss.

class Solution:
    def balancedStringSplit(self, s: str) -> int:
        return list(accumulate(1 if c == "R" else -1 for c in s)).count(0)
# Runtime: 28 ms, faster than 74.00% of Python3 online submissions for Split a String in Balanced Strings.
# Memory Usage: 13.8 MB, less than 62.73% of Python3 online submissions for Split a String in Balanced Strings.

What if I wrote this in an actual coding interview? If anything, the flow of designing the algorithm is difficult, so it may not be an issue. Is it correct to write the above long but sure method and a little vague?

If I receive it, I think I will probably choose the one that is correct. I don't want to cover it.

Up to here for this time. Thank you for your hard work!