Change Minimum Characters to Satisfy One of Three Conditions

Medium
1224.

Change Minimum Characters to Satisfy One of Three Conditions

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.

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:

  1. Every letter of a comes strictly before every letter of b in the alphabet.
  2. Every letter of b comes strictly before every letter of a in the alphabet.
  3. Both a and b consist 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^5
  • a and b consist only of lowercase English letters
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} a
 * @param {string} b
 * @return {number}
 */
var minCharacters = function(a, b) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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:

  1. Every letter of a comes strictly before every letter of b in the alphabet.
  2. Every letter of b comes strictly before every letter of a in the alphabet.
  3. Both a and b consist 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^5
  • a and b consist only of lowercase English letters

Hints for Change Minimum Characters to Satisfy One of Three Conditions

  1. Hint 1

    Only the letter counts of each string matter, not their positions.

  2. 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.

  3. Hint 3

    With counts and running prefix sums, each boundary costs O(1): characters of the low string above t plus characters of the high string at or below t. 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

  1. Build ca[26] and cb[26], the letter counts of a and b.
  2. Condition 3: for each letter c, the cost is len(a) + len(b) - ca[c] - cb[c]; keep the minimum.
  3. Sweep t from a to y (never z, since nothing can be strictly above z), keeping prefix sums pa and pb of the counts up to t.
  4. Condition 1 at t costs (len(a) - pa) + pb: letters of a above t must come down, letters of b at or below t must go up. Condition 2 costs (len(b) - pb) + pa.
  5. 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 t must stop at y: "strictly greater than z" is impossible, so t = z would 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 a and b are 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 best

Java

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