โปรแกรมเปลี่ยนตัวอักษรน้อยที่สุดเพื่อให้ผ่านเงื่อนไขหนึ่งในสามใน Python

ได้รับสตริง s, t ตัวพิมพ์เล็ก ใน 1 การดำเนินการ เปลี่ยนตัวอักษรใน s หรือ t ได้เป็นตัวพิมพ์เล็กใดๆ ต้องทำให้ผ่านเงื่อนไข 1 ใน 3:

1. ทุกตัวใน s น้อยกว่าทุกตัวใน t อย่างเคร่งครัด
2. ทุกตัวใน t น้อยกว่าทุกตัวใน s อย่างเคร่งครัด
3. ทั้ง s และ t มีตัวอักษรชนิดเดียวเท่านั้น

หาจำนวนการดำเนินการน้อยที่สุด

ตัวอย่าง: s="sts", t="uss" ผลลัพธ์ 2

วิธีแก้ปัญหา

1. นับความถี่ตัวอักษรใน s, t
2. วนตัวอักษร a..z คำนวณสะสม:
   • unique: เปลี่ยนทั้งคู่ให้เป็นตัวอักษรเดียวกัน
   • less_s: เปลี่ยน s ให้ทุกตัว > t
   • less_t: เปลี่ยน t ให้ทุกตัว > s
3. คืนค่า min ของทั้งสาม

ตัวอย่างโค้ด

from collections import Counter
import string

def solve(s, t):
    counter_s = Counter(s)
    counter_t = Counter(t)
    less_s, less_t, unique = float('inf'), float('inf'), float('inf')
    accu_s, accu_t = 0, 0
    for c in string.ascii_lowercase:
        unique = min(unique, len(s)+len(t)-counter_s[c]-counter_t[c])
        if c > 'a':
            less_s = min(less_s, len(s)-accu_s+accu_t)
            less_t = min(less_t, len(t)-accu_t+accu_s)
        accu_s += counter_s[c]
        accu_t += counter_t[c]
    return min(less_s, less_t, unique)

s = "sts"
t = "uss"
print(solve(s, t))

อินพุต

"sts", "uss"

เอาต์พุต

2