PythonでBの前にAを作成するために削除する文字の最小数を見つけるプログラム

2文字のAとBのみで構成される文字列sがあるとすると、Bのすべての出現の前にAsのすべての出現を取得するために、sから削除する必要のある文字の最小数を見つける必要があります。

したがって、入力がS ="AABAABB"の場合、最後のAを削除してAABBBを取得できるため、出力は1になります。

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

• a_right：=s内の「A」の出現回数

• b_left：=0

• ans：=a_right

• sの各インデックスiと文字cについて、実行します

  • cが「A」と同じ場合

    • a_right：=a_right-1

  • それ以外の場合

    • b_left：=b_left + 1

  • ans：=最小のansとa_right + b_left

• ansを返す

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

例

class Solution:
   def solve(self, s):
      a_right = s.count("A")
      b_left = 0

      ans = a_right
      for i, c in enumerate(s):
         if c == "A":
            a_right -= 1
         else:
            b_left += 1
         ans = min(ans, a_right + b_left)
      return ans

ob = Solution()
S = "AABAABB"
print(ob.solve(S))

入力

"AABAABB"

出力

1