Change Minimum Characters to Satisfy One of Three Conditions

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:

Return the minimum number of operations needed to achieve your goal.

 

Example 1:

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:

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

Constraints:


Solution:

option3 is trivial to calculate
for option1 and 2, first calculate countmaps for both strings, for example,
if a = "aba", b = "caa",
then we have
 [2 1 0]
 [2 0 1]
calculate prefix sum on both coutmaps, we get
 -  a b c 
[0 2 3 3]
[0 2 2 3]
to make a smaller than b, we can pick one pivot char in a, and make all chars in a small or equal to the pivot, and make all chars in b greater than the pivot,
if we pick char a as the pivot for example,
the number of ops to make all chars in a <= a is prefix[-1] - prefix[1] (which is a) = 3 - 2 = 1
the number of ops to make all chars in b > a is prefix[1] = 2
so the total number of operations is 1 + 2 = 3
if we pick char b is pivot, then
ops to make all chars in a <= b is 3 - 3 = 0
ops to make all chars in c > b = 2
total number ops is 2
if we pick char c,
then  in a, <= c is 0
> c = 3
total is 3,
so for option1, we have min of 2

we can calculate option2 with same method 




class Solution {
    public int minCharacters(String a, String b) {
        int[] counta = new int[26];
        int[] countb = new int[26];
        int m = a.length(), n = b.length();
        int maxa = 0, maxb = 0;
        for (int i = 0; i < m; i ++) {
            counta[a.charAt(i) - 'a'] ++;
            maxa = Math.max(maxa, counta[a.charAt(i) - 'a']);
        }
        for (int i = 0; i < n; i ++) {
            countb[b.charAt(i) - 'a'] ++;
            maxb = Math.max(maxb, countb[b.charAt(i) - 'a']);
        }
        // a: [2, 1, 0]
        // [0  2  3  3]
        // b: [2, 0, 1]
        // [0  2  2  3]
        //
        // a: [2 1 0 3]
        //  0  2 3 3 6 
        // b: [1 0 1 1]
        //  0  1 1 2 3
        int option1 = makeASmaller(counta, countb);
        int option2 = makeASmaller(countb, counta);
        int option3 = m - maxa + n - maxb;
        // System.out.println(Arrays.asList(option1, option2, option3));
        return Math.min(option1, Math.min(option2, option3));
        // return option1;
    }
    
    private int makeASmaller(int[] a, int [] b) {
        int[] prefixa = new int[27];
        int[] prefixb = new int[27];
        for (int i = 1; i < 27; i ++) {
            prefixa[i] = prefixa[i - 1] + a[i - 1];
            prefixb[i] = prefixb[i - 1] + b[i - 1];
        }   
        int res = 1000000;
        // System.out.println(Arrays.toString(prefixa));
        // System.out.println(Arrays.toString(prefixb));
        for (int i = 1; i < 26; i ++) {
            int incB = prefixb[i];
            int decA = prefixa[26] - prefixa[i];
            // System.out.println(i + ", " + incB + ", " + decA);
            res = Math.min(res, incB + decA);
        }
        return res;
    }
}