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.

Your goal is to satisfy one of the following three conditions:

  • Every letter in a is strictly less than every letter in b in the alphabet.
  • Every letter in b is strictly less than every letter in a in the alphabet.
  • Both a and b consist of only one distinct letter.

Return theminimum number of operations needed to achieve your goal.

Examples

Example 1

1
2
3
4
5
6
7

Input: a = "aba", b = "caa"
Output: 2
Explanation: Consider the best way to make each condition true:
1) Change b to "ccc" in 2 operations, then every letter in a is less than every letter in b.
2) Change a to "bbb" and b to "aaa" in 3 operations, then every letter in b is less than every letter in a.
3) Change a to "aaa" and b to "aaa" in 2 operations, then a and b consist of one distinct letter.
The best way was done in 2 operations (either condition 1 or condition 3).

Example 2

1
2
3

Input: a = "dabadd", b = "cda"
Output: 3
Explanation: The best way is to make condition 1 true by changing b to "eee".

Constraints

  • 1 <= a.length, b.length <= 10^5
  • a and b consist only of lowercase letters.

Solution

Method 1 – Prefix Sums and Frequency Counting

Intuition

We want to minimize the number of changes to make one of three conditions true. For the first two conditions, we can use prefix sums to efficiently count how many characters need to be changed to make all of one string less than all of the other. For the third condition, we count the most frequent character in both strings and try to make all characters the same.

Approach

  1. Count the frequency of each letter (a-z) in both strings.
  2. Build prefix sums for both frequency arrays.
  3. For conditions 1 and 2, try every possible split point (from ‘a’+1 to ‘z’) and calculate the number of changes needed.
  4. For condition 3, try every letter and count how many changes are needed to make both strings consist of only that letter.
  5. Return the minimum among all options.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    public int minCharacters(String a, String b) {
        int[] ca = new int[26], cb = new int[26];
        for (char ch : a.toCharArray()) ca[ch - 'a']++;
        for (char ch : b.toCharArray()) cb[ch - 'a']++;
        int n = a.length(), m = b.length(), ans = n + m;
        int[] pa = new int[27], pb = new int[27];
        for (int i = 0; i < 26; i++) {
            pa[i+1] = pa[i] + ca[i];
            pb[i+1] = pb[i] + cb[i];
        }
        for (int i = 1; i < 26; i++) {
            ans = Math.min(ans, n - pa[i] + pb[i]);
            ans = Math.min(ans, m - pb[i] + pa[i]);
        }
        for (int i = 0; i < 26; i++) {
            ans = Math.min(ans, n + m - ca[i] - cb[i]);
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution:
    def minCharacters(self, a: str, b: str) -> int:
        ca = [0] * 26
        cb = [0] * 26
        for ch in a:
            ca[ord(ch) - ord('a')] += 1
        for ch in b:
            cb[ord(ch) - ord('a')] += 1
        n, m = len(a), len(b)
        pa = [0] * 27
        pb = [0] * 27
        for i in range(26):
            pa[i+1] = pa[i] + ca[i]
            pb[i+1] = pb[i] + cb[i]
        ans = n + m
        for i in range(1, 26):
            ans = min(ans, n - pa[i] + pb[i])
            ans = min(ans, m - pb[i] + pa[i])
        for i in range(26):
            ans = min(ans, n + m - ca[i] - cb[i])
        return ans

Complexity

  • ⏰ Time complexity: O(n + m + 26)
  • 🧺 Space complexity: O(26)