Change Minimum Characters to Satisfy One of Three Conditions — LeetCode 1737 Python Solution
MediumHash TableStringCountingPrefix Sum
- Problem
- #1737
- Pattern
- Prefix Sum
- Reading time
- 4 min
- Source
- leetcode.com
The problem
You are given two strings a and b that consist of lowercase letters. In one operation, you can change any character in a or b to any lowercase letter.
Example
- Input
- a = "aba", b = "caa"
- Output
- 2
- Explanation
- Consider the best way to make each condition true:
Python solution
Python
class Solution:
def minCharacters(self, a: str, b: str) -> int:
def f(cnt1, cnt2):
for i in range(1, 26):
t = sum(cnt1[i:]) + sum(cnt2[:i])
nonlocal ans
ans = min(ans, t)
m, n = len(a), len(b)
cnt1 = [0] * 26
cnt2 = [0] * 26
for c in a:
cnt1[ord(c) - ord('a')] += 1
for c in b:
cnt2[ord(c) - ord('a')] += 1
ans = m + n
for c1, c2 in zip(cnt1, cnt2):
ans = min(ans, m + n - c1 - c2)
f(cnt1, cnt2)
f(cnt2, cnt1)
return ansComplexity
| Measure | Complexity |
|---|---|
| Time | O(m + n + C^2), where m and n are the lengths of strings a and b respectively, and C is the size of the character set |
| Space | O(n) auxiliary |
Pattern: Prefix Sum
Precompute running totals once so any range query becomes a single subtraction. LeetCode 1737. Change Minimum Characters to Satisfy One of Three Conditions is filed here because LeetCode tags it Prefix Sum, which is the vocabulary this hub collects.
The prefix sum guide has the Python template for the pattern and the 157 LeetCode problems that use it.
Related problems
Frequently asked questions
- How hard is LeetCode 1737. Change Minimum Characters to Satisfy One of Three Conditions?
- LeetCode 1737. Change Minimum Characters to Satisfy One of Three Conditions is rated Medium on LeetCode.
- What is the time complexity of LeetCode 1737. Change Minimum Characters to Satisfy One of Three Conditions?
- The Python solution on this page runs in O(m + n + C^2), where m and n are the lengths of strings a and b respectively, and C is the size of the character set.
- What is the space complexity of LeetCode 1737. Change Minimum Characters to Satisfy One of Three Conditions?
- The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 1737. Change Minimum Characters to Satisfy One of Three Conditions cover?
- LeetCode 1737. Change Minimum Characters to Satisfy One of Three Conditions is tagged Hash Table, String, Counting and Prefix Sum on LeetCode.