โปรแกรมปรับสมดุลสตริงทิศทางเพื่อให้แต่ละทิศทางเกิดขึ้นไตรมาสครั้งในPython

สมมติว่าเรามีสตริง s ที่มีสี่ทิศทาง "N", "S", "W" และ "E" สำหรับ North, South, West และ East ตามลำดับ เราต้องหาขนาดของสตริงย่อยที่สั้นที่สุดที่เราสามารถอัปเดตได้ โดยแต่ละทิศทางจากสี่ทิศทางจะเกิดขึ้น n/4 ครั้งในแต่ละอัน โดยที่ n คือขนาดของสตริง s

ดังนั้น หากอินพุตเป็นเหมือน s ="NNSWWESN" ผลลัพธ์จะเป็น 1 โดยที่ n คือ 8 ดังนั้น 8/4 จึงเป็น 2 ดังนั้นหากเราเปลี่ยน N สุดท้ายเป็น E ทิศทางทั้งหมดจะมีสองครั้ง

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• n :=ขนาดของ s
• ถ้า n เป็น 0 แล้ว
  • คืน 0
• ควอเตอร์ :=ชั้นของ (n / 4)
• count :=รายการที่มีความถี่ของแต่ละองค์ประกอบที่มีอยู่ใน s
• เป้าหมาย :=แผนที่ใหม่
• สำหรับแต่ละคู่ (dir, cnt) ในการนับ ทำ
  • ถ้า cnt> ไตรมาส แล้ว
    • target[dir] :=ไตรมาส - cnt
• ถ้าเป้าหมายว่างเปล่า
  • คืน 0
• ซ้าย :=0
• min_len :=inf
• สำหรับแต่ละดัชนีขวาและทิศทาง dir ใน s ทำ
  • ถ้า dir อยู่ในเป้าหมายแล้ว
    • target[dir] :=target[dir] + 1
  • ในขณะที่รายการค่าเป้าหมายขั้นต่ำทั้งหมด>=0, ทำ
    • min_len :=ขั้นต่ำของ min_len และ (ขวา - ซ้าย + 1)
    • ถ้า s[ซ้าย] ในเป้าหมาย แล้ว
      • target[s[left]] :=target[s[left]] - 1
      • ซ้าย :=ซ้าย + 1
• ส่งคืน min_len

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

from collections import Counter
def solve(s):
   n = len(s)

   if not n:
      return 0
   quarter = n // 4

   count = Counter(s)
   target = dict()
   for (dir, cnt) in count.items():
      if cnt > quarter:
         target[dir] = quarter - cnt

   if not target:
      return 0

   left, min_len = 0, float("inf")
   for right, dir in enumerate(s):
      if dir in target:
         target[dir] += 1

      while min(target.values()) >= 0:
         min_len = min(min_len, right - left + 1)
         if s[left] in target:
            target[s[left]] -= 1
         left += 1

   return min_len

s = "NNSWWESN"
print(solve(s))

อินพุต

"NNSWWESN"

ผลลัพธ์

1