Pythonで各文字が最大で1つの部分に表示されるリストの各パーティションのサイズを見つけるプログラム

小文字の文字列sがあるとすると、sをできるだけ多くの部分に分割して、各文字が最大で1つの部分に表示され、パーティションのサイズをリストとして見つけることができます。

したがって、入力がs ="momoplaykae"の場合、文字列が["momo"、 "p"、 "l"、 "に分割されるため、出力は[4、1、1、4、1]になります。 ayka "、"e"]。

これを解決するには、次の手順に従います-

• count：=s内の文字とその出現を含むマップ

• out：=新しいリスト、stk：=空のスタック

• 長さ：=0

• sの各文字について、実行します

  • count [char]：=count [char]-1

  • 長さ：=長さ+ 1

  • count [char]が0と同じでないか、stkが空でない場合は、実行してください

    • count [char]が0と同じでない場合、

      • charをstkにプッシュ

      • ループから出てきます

    • stkが空でなく、count [top of stk]が0と同じ場合、

      • stkからポップ

    • それ以外の場合

      • ループから出てきます

  • stkが空で、count [char]が0と同じ場合、

    • アウト後に長さを挿入

    • 長さ：=0

• 戻る

例

理解を深めるために、次の実装を見てみましょう-

from collections import Counter
class Solution:
   def solve(self, s):
      count = Counter(s)
      out = []
      stk = []
      length = 0
      for char in s:
         count[char] -= 1
         length += 1
         while count[char] != 0 or stk:
            if count[char] != 0:
               stk.append(char)
               break
            if stk and count[stk[-1]] == 0:
               stk.pop()
            else:
               break
            if not stk and count[char] == 0:
               out += [length]
               length = 0
         return out
ob = Solution()
s = "momoplaykae"
print(ob.solve(s))

入力

"momoplaykae"

出力

[4, 1, 1, 4, 1]