ゼロから始めるLeetCode Day59 「1221. Split a String in Balanced Strings」

概要

海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。

どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。

早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。

と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。

ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。

Leetcode

Python3で解いています。
Twitterやってます。

ゼロから始めるLeetCode 目次

前回
ゼロから始めるLeetCode Day58 「20. Valid Parentheses」
次回
ゼロから始めるLeetCode Day60「1481. Least Number of Unique Integers after K Removals」

Twitterやってます。

問題

1221. Split a String in Balanced Strings

難易度はEasy。

問題としては、文字列sが与えられます、この文字列の中には'L'か'R'しか入っていません。
これらの文字数が等しい文字列を最大量のバランスが取れた文字列で分割し、その分割の最大量を返してください。

自分で翻訳しててもわかりづらいのでとりあえず例を見てみましょう。

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’

こうすると分かりやすいですね。

解法

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.

二つ変数を用意して差し引きをするだけ！

対戦ありがとうございました。

というのもあれなので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.

こういうのって実際のコーディング面接で書いたらどうなるんでしょうね？
どっちかというとアルゴリズムを設計するフローが大変なので論点にはならないかもしれませんが。
上のような長いけど確実な方法と少しあやふやだけどこういう書き方をするのが正しいのか。

僕が受けるならおそらく間違いがない方を選んでしまう気がします。
あたふたしたくないですし。

今回はここまで。お疲れ様でした！