สมมติว่าเรามีสตริงที่ประกอบด้วยตัวอักษร A และ B เพียงสองตัว เราต้องหาจำนวนตัวอักษรขั้นต่ำที่ต้องลบออกจาก s เพื่อให้ได้ค่า As ก่อนการเกิด B ทั้งหมด
ดังนั้นหากอินพุตเป็น S ="AABAABB" ผลลัพธ์จะเป็น 1 เนื่องจากเราสามารถลบ A สุดท้ายเพื่อรับ AABBB
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้:
-
a_right :=จำนวนครั้งของ "A" ใน s
-
b_left :=0
-
ตอบ :=a_right
-
สำหรับแต่ละดัชนี i และอักขระ c ใน s ทำ
-
ถ้า c เหมือนกับ "A" แล้ว
-
a_right :=a_right - 1
-
-
มิฉะนั้น
-
b_left :=b_left + 1
-
-
ans :=ขั้นต่ำของ ans และ a_right + b_left
-
-
กลับมาอีกครั้ง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น:
ตัวอย่าง
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
