Leetcode-1737- minimum number of characters to change if one of the three conditions is met

subject

Here are two strings  a  and  b , Both are made up of small letters . In one step , You can take  a  or  b  Medium   Any character   Change for   Any lowercase letter  .

The ultimate goal of the operation is to satisfy the following three conditions   One of  ：

• a  Medium   Every letter   In the alphabet   Strictly less than  b  Medium   Every letter  .
• b  Medium   Every letter   In the alphabet   Strictly less than  a  Medium   Every letter  .
• a  and  b  all   from   The same   Alphabetic composition .

Return to what you need to achieve your goals   least   Operands .

Example 1：

 Input ：a = "aba", b = "caa"
 Output ：2
 explain ： The best solutions to meet each condition are ：
1)  take  b  Turn into  "ccc",2  operations , Satisfy  a  Every letter in is less than  b  Every letter in ;
2)  take  a  Turn into  "bbb"  And will  b  Turn into  "aaa",3  operations , Satisfy  b  Every letter in is less than  a  Every letter in ;
3)  take  a  Turn into  "aaa"  And will  b  Turn into  "aaa",2  operations , Satisfy  a  and  b  It's made up of the same letter .
 The best solution is just  2  operations （ Meet the conditions  1  Or the conditions  3）.

Example 2：

 Input ：a = "dabadd", b = "cda"
 Output ：3
 explain ： Meet the conditions  1  The best solution is to  b  Turn into  "eee" .

 

Tips ：

• 1 <= a.length, b.length <= 105
• a  and  b  It's just small letters

Topic link ： Address

 

analysis

1. First, use two arrays Put two strings Hash turn ,<key: Lowercase letters , value: The number of this letter in the string >,

So each array size only needs 26

( I use 27 Because I didn't want to declare two more variables )

2. Traverse hash map, Find the minimum operand

If at this time To meet condition one ,

namely A Every letter in the string is less than B Every letter in the string ,

You need to A In a string Blue Part of the corresponding letters are replaced by green The corresponding letter ( Any replacement ), take B In a string Blue Part of the corresponding letters are replaced by green The corresponding letter ( Any replacement ).

If at this time Meet condition 2 ,

namely B Every letter in the string is less than A Every letter in the string ,

You need to A In a string The green part Replace the corresponding letter with Blue The corresponding letter ( Any replacement ), take B In a string green Part of the corresponding letters are replaced by Blue The corresponding letter ( Any replacement ).

The final effect is shown in the figure below ：

A Number of replacements +B Number of replacements = The number of operands required to achieve the goal .

therefore Minimum operand = min(" The operands required to satisfy condition one ", " The operands required to satisfy condition 2 ");

 

If you want to Meet condition 3 ：

for example ： take A、B Are replaced by “ It's made up of lowercase letters c The string formed ”

About to remove ‘c’ Replace all letters except with ‘c’ The cost .

for example ："abcde" and "pppc" To meet condition 3, you need to do 4+3 Sub permutation .

 

On the whole , From lower case letters a Traverse to lowercase letters y( No z, This can be verified by drawing ), Is to find the minimum value under any condition .

Code

class Solution {
    public int minCharacters(String a, String b) {
        int[] arr = new int[27];
        int[] brr = new int[27];
        int len_a = a.length(), len_b = b.length(), result = Integer.MAX_VALUE;
        for(int i = 0; i < a.length(); i++){
            arr[a.charAt(i) - 'a']++;
        }
        for(int i = 0; i < b.length(); i++){
            brr[b.charAt(i) - 'a']++;
        }

        for(int i = 0; i < 25; i++) {
            arr[26] += arr[i];
            brr[26] += brr[i];
            result = Math.min(Math.min(result, len_a + len_b - arr[i] -brr[i]), Math.min(brr[26] + len_a - arr[26], arr[26] + len_b - brr[26]));
        }
        return Math.min(result, len_a + len_b - arr[25] -brr[25]);
    }
}