โปรแกรมเปลี่ยนอักขระขั้นต่ำเพื่อให้เป็นไปตามหนึ่งในสามเงื่อนไขใน Python

สมมติว่าเรามีสตริง s และ t สองสตริงที่มีตัวพิมพ์เล็กเท่านั้น ในการดำเนินการครั้งเดียว เราสามารถเปลี่ยนอักขระใดก็ได้ใน s หรือ t เป็นอักษรตัวพิมพ์เล็ก เราต้องปฏิบัติตามหนึ่งในสามเงื่อนไขต่อไปนี้ -

• ตัวอักษรใน s ทุกตัวมีขนาดเล็กกว่าตัวอักษรทุกตัวใน t อย่างเคร่งครัด

• ตัวอักษรใน t ทุกตัวมีขนาดเล็กกว่าตัวอักษรทุกตัวใน s อย่างเคร่งครัด

• ทั้ง s และ t ประกอบด้วยตัวอักษรที่แตกต่างกันเพียงตัวเดียว

เราต้องหาจำนวนขั้นต่ำของการดำเนินการที่จำเป็นเพื่อให้ได้ผลลัพธ์

ดังนั้น หากอินพุตเป็น s ="sts", t ="uss" ผลลัพธ์จะเป็น 2 เพราะ

• หากเราเปลี่ยน t เป็น "uuu" ใน 2 การดำเนินการ ดังนั้นทุกตัวอักษรใน s จะน้อยกว่าทุกตัวอักษรใน t

• หากเราเปลี่ยน s เป็น "ttt" และ t เป็น "sss" ในการดำเนินการ 3 ครั้ง ดังนั้นทุกตัวอักษรใน t จะน้อยกว่าทุกตัวอักษรใน s

• หากเราเปลี่ยน s เป็น "sss" และ t เป็น "sss" ใน 2 การดำเนินการ ดังนั้น s และ t จะประกอบด้วยตัวอักษรที่แตกต่างกันเพียงตัวเดียว

นี่คือวิธีที่ดีที่สุดในการดำเนินการ 2 ครั้ง (1 หรือ 3)

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

• counter_s :=แผนที่เพื่อเก็บความถี่ของอักขระแต่ละตัวใน s
• counter_t :=แผนที่เพื่อเก็บความถี่ของอักขระแต่ละตัวใน t
• less_s :=อินฟินิตี้, less_t :=อินฟินิตี้ :=อินฟินิตี้
• accu_s :=0, accu_t :=0
• สำหรับอักขระ c แต่ละตัวในภาษาอังกฤษตัวพิมพ์เล็ก do
  • unique :=ขั้นต่ำของ unique และ (ขนาด s + ขนาดของ t - counter_s[c] - counter_t[c])
    • counter_t[c])
  • ถ้า ascii ของ c มากกว่า ascii ของ 'a' แล้ว
    • less_a :=ขั้นต่ำ less_s และ (ขนาดของ s - accu_s + accu_t)
    • less_b :=ขั้นต่ำ less_t และ (ขนาดของ t - accu_t + accu_s)
  • accu_s :=accu_s + counter_s[c]
  • accu_t :=accu_t + counter_t[c]
• คืนค่าขั้นต่ำของ less_s, less_t และไม่ซ้ำกัน

ตัวอย่าง

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

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

อินพุต

"sts", "uss"

ผลลัพธ์

2