Chương trình thay đổi tối thiểu ký tự để thỏa mãn một trong ba điều kiện trong Python

Mô tả bài toán

Cho hai chuỗi s, t chỉ chứa chữ thường. Một phép toán: thay đổi một ký tự bất kỳ thành chữ thường khác. Cần thỏa mãn một trong ba điều kiện:

1. Mọi ký tự trong s < nhỏ hơn mọi ký tự trong t.
2. Mọi ký tự trong t < nhỏ hơn mọi ký tự trong s.
3. Cả s và t chỉ chứa một ký tự duy nhất.

Tìm số phép toán tối thiểu.

Ví dụ

s = "sts", t = "uss" -> đầu ra 2 (đổi t thành "uuu" hoặc đổi cả hai thành "sss").

Giải thuật

1. Đếm tần suất ký tự trong s và t.
2. Duyệt qua 'a' đến 'z', tính:
   • unique: số thay đổi để cả hai chỉ chứa ký tự c.
   • less_s: số thay đổi để mọi ký tự s < t (ngưỡng tại c).
   • less_t: số thay đổi để mọi ký tự t < s.
3. Trả về min của ba giá trị trên.

Triển khai Python

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))

Đầu vào

"sts", "uss"

Đầu ra

2