Change Minimum Characters to Satisfy One of Three Conditions Solution
Change Minimum Characters to Satisfy One of Three Conditions solution: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Change Minimum Characters to Satisfy One of Three Conditions is a medium coding problem on strings, hash table and prefix sum, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Strings, Hash Table, Prefix Sum, Counting
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given two strings a and b made of lowercase English letters. In one operation you may pick any character of either string and change it to any lowercase letter.
Your goal is to make at least one of these three conditions true:
- Every letter of
acomes strictly before every letter ofbin the alphabet. - Every letter of
bcomes strictly before every letter ofain the alphabet. - Both
aandbconsist of one and the same letter repeated.
Return the minimum number of operations needed.
Example 1
Input: a = "code", b = "kairo"
Output: 2
Explanation: Change the `o` of `a` to `a` and the `a` of `b` to `z`: now `a` = "cade" uses only letters up to `e` and `b` = "kziro" only letters after `e`, so condition 1 holds.
Example 2
Input: a = "zz", b = "zzz"
Output: 0
Explanation: Both strings are already the single letter `z`, so condition 3 holds.
Example 3
Input: a = "ab", b = "ba"
Output: 2
Constraints
1 <= a.length, b.length <= 10^5a and b consist only of lowercase English letters
Hints for Change Minimum Characters to Satisfy One of Three Conditions
Hint 1
Only the letter counts of each string matter, not their positions.
Hint 2
Conditions 1 and 2 are about a boundary letter: one string must sit at or below some letter
t, the other strictly above it. Try all 25 boundaries.Hint 3
With counts and running prefix sums, each boundary costs O(1): characters of the low string above
tplus characters of the high string at or belowt. Condition 3 keeps the letter with the largest combined count.
How to solve Change Minimum Characters to Satisfy One of Three Conditions
Count the 26 letters of each string. Every condition then has a closed-form cost: condition 3 keeps the most common shared letter, and conditions 1 and 2 pick a boundary letter t and move everything on the wrong side of it.
Approach
- Build
ca[26]andcb[26], the letter counts ofaandb. - Condition 3: for each letter
c, the cost islen(a) + len(b) - ca[c] - cb[c]; keep the minimum. - Sweep
tfromatoy(neverz, since nothing can be strictly abovez), keeping prefix sumspaandpbof the counts up tot. - Condition 1 at
tcosts(len(a) - pa) + pb: letters ofaabovetmust come down, letters ofbat or belowtmust go up. Condition 2 costs(len(b) - pb) + pa. - Return the smallest cost seen.
Why it works
Condition 1 holds exactly when there is a letter t with all of a at or below t and all of b above it, so trying every t covers every way to satisfy it. For a fixed t, a character on the correct side never needs to change and each character on the wrong side needs exactly one operation, so the cost is precisely the count of misplaced characters. The same argument applies to condition 2 and, with a fixed target letter, to condition 3.
Complexity
- Time —
O(len(a) + len(b) + 26) - Space —
O(26)
Pitfalls
- The boundary
tmust stop aty: "strictly greater thanz" is impossible, sot = zwould count a free win that does not exist. - Condition 3 needs both strings to use the same letter, not each string a single letter of its own.
- Do not forget condition 2 — the roles of
aandbare not symmetric in the input.
Reference solution
Python
def minCharacters(a: str, b: str) -> int:
ca = [0] * 26
cb = [0] * 26
for ch in a:
ca[ord(ch) - 97] += 1
for ch in b:
cb[ord(ch) - 97] += 1
m, n = len(a), len(b)
best = m + n - max(ca[c] + cb[c] for c in range(26))
pa = pb = 0
for t in range(25):
pa += ca[t]
pb += cb[t]
best = min(best, (m - pa) + pb, (n - pb) + pa)
return bestJava
public static int minCharacters(String a, String b) {
int[] ca = new int[26], cb = new int[26];
for (int i = 0; i < a.length(); i++) ca[a.charAt(i) - 'a']++;
for (int i = 0; i < b.length(); i++) cb[b.charAt(i) - 'a']++;
int m = a.length(), n = b.length();
int best = m + n;
for (int c = 0; c < 26; c++) best = Math.min(best, m + n - ca[c] - cb[c]);
int pa = 0, pb = 0;
for (int t = 0; t < 25; t++) {
pa += ca[t];
pb += cb[t];
best = Math.min(best, Math.min(m - pa + pb, n - pb + pa));
}
return best;
}C++
int minCharacters(string a, string b) {
int ca[26] = {0}, cb[26] = {0};
for (char ch : a) ca[ch - 'a']++;
for (char ch : b) cb[ch - 'a']++;
int m = a.size(), n = b.size();
int best = m + n;
for (int c = 0; c < 26; c++) best = min(best, m + n - ca[c] - cb[c]);
int pa = 0, pb = 0;
for (int t = 0; t < 25; t++) {
pa += ca[t];
pb += cb[t];
best = min(best, min(m - pa + pb, n - pb + pa));
}
return best;
}JavaScript
var minCharacters = function(a, b) {
var ca = new Array(26).fill(0), cb = new Array(26).fill(0);
for (var i = 0; i < a.length; i++) ca[a.charCodeAt(i) - 97]++;
for (var j = 0; j < b.length; j++) cb[b.charCodeAt(j) - 97]++;
var m = a.length, n = b.length;
var best = m + n;
for (var c = 0; c < 26; c++) best = Math.min(best, m + n - ca[c] - cb[c]);
var pa = 0, pb = 0;
for (var t = 0; t < 25; t++) {
pa += ca[t];
pb += cb[t];
best = Math.min(best, m - pa + pb, n - pb + pa);
}
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Hashing: Hash Maps and Hash Sets