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

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

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

ขั้นตอนการแก้ปัญหา

1. n := ขนาดของ s
2. ถ้า n == 0 คืนค่า 0
3. quarter := floor(n / 4)
4. count := รายการความถี่ของแต่ละสมาชิกใน s
5. target := แมปใหม่
6. สำหรับแต่ละคู่ (dir, cnt) ใน count:
   • ถ้า cnt > quarter ให้ target[dir] := quarter - cnt
7. ถ้า target ว่าง คืนค่า 0
8. left := 0, min_len := inf
9. สำหรับแต่ละดัชนี right และทิศทาง dir ใน s:
   • ถ้า dir อยู่ใน target ให้ target[dir] += 1
   • ในขณะที่ min(target.values()) >= 0:
     • min_len := min(min_len, right - left + 1)
     • ถ้า s[left] อยู่ใน target ให้ target[s[left]] -= 1, left += 1
10. คืนค่า 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