Python에서 세 가지 조건 중 하나를 충족하도록 최소 문자를 변경하는 프로그램

<시간/>

소문자만 포함된 두 개의 문자열 s와 t가 있다고 가정합니다. 한 번의 작업으로 s 또는 t의 모든 문자를 소문자로 변경할 수 있습니다. 다음 세 가지 조건 중 하나를 충족해야 합니다. -

s의 모든 문자는 알파벳의 t에 있는 모든 문자보다 엄격하게 작습니다.
t의 모든 문자는 알파벳의 s에 있는 모든 문자보다 엄격하게 작습니다.
s와 t는 모두 하나의 고유한 문자로만 구성됩니다.

결과를 얻기 위해 필요한 최소 작업 수를 찾아야 합니다.

따라서 입력이 s ="sts", t ="uss"와 같으면 출력은 2가 됩니다.

2번의 연산으로 t를 "uuu"로 변경하면 s의 모든 문자는 t의 모든 문자보다 작습니다.
3번의 연산으로 s를 "ttt"로, t를 "sss"로 변경하면 t의 모든 문자는 s의 모든 문자보다 작습니다.
2번의 연산으로 s를 "sss"로, t를 "sss"로 바꾸면 s와 t는 하나의 별개의 문자로 구성됩니다.

여기에서 가장 좋은 방법은 2가지 작업(1 또는 3)으로 수행되었습니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

counter_s :=s에 있는 각 문자의 빈도를 유지하기 위한 맵
counter_t :=t에 있는 각 문자의 빈도를 유지하기 위한 맵
less_s :=무한대, less_t :=무한대, 고유 :=무한대
accu_s :=0, accu_t :=0
영어 소문자의 각 문자 c에 대해 다음을 수행합니다.
- unique :=고유의 최소값 및 (s의 크기 + t의 크기 - counter_s[c] - counter_t[c])
  - counter_t[c])
- c의 ASCII가 'a'의 ASCII보다 크면
  - 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_t, less_t 및 unique의 최소값을 반환합니다.

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

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"