Chương trình thay đổi các ký tự tối thiểu để đáp ứng một trong ba điều kiện trong Python

Giả sử chúng ta có hai chuỗi s và t chỉ có các chữ cái thường. Trong một thao tác, chúng ta có thể thay đổi bất kỳ ký tự nào trong s hoặc t thành bất kỳ ký tự viết thường nào. Chúng ta phải thỏa mãn một trong ba điều kiện sau -

• Mọi chữ cái trong s đều nhỏ hơn mọi chữ cái trong bảng chữ cái.

• Mọi ký tự trong t đều nhỏ hơn mọi ký tự s trong bảng chữ cái.

• Cả s và t chỉ bao gồm một chữ cái riêng biệt.

Chúng tôi phải tìm số lượng thao tác tối thiểu cần thiết để có được kết quả.

Vì vậy, nếu đầu vào là s =​​"sts", t ="uss", thì đầu ra sẽ là 2 vì

• Nếu chúng ta thay đổi t thành "uuu" trong 2 phép toán, thì mọi chữ cái trong s đều nhỏ hơn mọi chữ cái trong t.

• Nếu chúng ta thay đổi s thành "ttt" và t thành "sss" trong 3 phép toán, thì mọi chữ cái trong t đều ít hơn mọi chữ cái trong s.

• Nếu chúng ta thay đổi s thành "sss" và t thành "sss" trong 2 phép toán, thì s và t bao gồm một chữ cái riêng biệt.

Đây là cách tốt nhất được thực hiện trong 2 hoạt động (1 hoặc 3).

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• counter_s:=ánh xạ để lưu giữ tần số của từng ký tự trong s
• counter_t:=ánh xạ để lưu giữ tần số của từng ký tự trong t
• less_s:=infinity, less_t:=infinity, unique:=infinity
• acquy_s:=0, acquy_t:=0
• đối với mỗi ký tự c bằng ký tự tiếng Anh viết thường, hãy thực hiện
  • unique:=tối thiểu là duy nhất và (kích thước của s + kích thước của t - counter_s [c] - counter_t [c])
    • counter_t [c])
  • nếu ascii của c lớn hơn ascii của 'a', thì
    • less_a:=tối thiểu là less_s và (kích thước của s - Accu_s + Accu_t)
    • less_b:=tối thiểu của less_t và (kích thước của t - Accu_t + Accu_s)
  • acquy_s:=acquy_s + counter_s [c]
  • Accu_t:=Accu_t + counter_t [c]
• trả về tối thiểu less_s, less_t và duy nhất

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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_a = min(less_s, len(s) - accu_s + accu_t)
         less_b = 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