[high frequency interview questions] difficulty 1/5, popular enumeration simulation questions

Title Description

This is a LeetCode Upper 「1737. The minimum number of characters to be changed to satisfy one of the three conditions 」, The difficulty is 「 secondary 」.

Tag : 「 enumeration 」、「 Count 」、「 simulation 」

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

Copy

Example 2：

 Input ：a = "dabadd", b = "cda"

 Output ：3

 explain ： Meet the conditions  1  The best solution is to  b  Turn into  "eee" .

Copy

Tips ：

1 <= a.length, b.length <= 10^5

• a and b It's just small letters

Count + enumeration

Use c1 and c2 The string a and b Conduct word frequency statistics respectively , Record string a and b The length of is

n

and

m

.

Then enumerate the characters

i

（ Lowercase letters a-z）, Count the modification times of the three cases respectively ：

1. Corresponding conditions

1

： The purpose is to convert the string a All the characters in become 「 Strictly less than 」 character

i

, The string b All characters in become 「 Not less than / Greater than or equal to 」 character

i

. This can be counted separately a Medium size meets 「 Greater than or equal to 」 character

i

Number of characters , as well as b Medium size meets 「 Less than 」 character

i

Number , The sum of the two is the minimum number of modifications that satisfy the condition . Be careful , When

i = 0

（ It means enumerating to lowercase letters

a

） when , Need to skip , Because there is no value size 「 Strictly less than 」 Letter

a

The characters of , That is, it is impossible to replace a string with all characters 「 Strictly less than 」 Letter

a

;

1. Corresponding conditions

2

： And conditions

1

Empathy ;

1. Corresponding conditions

3

： If you want to change all the characters of two characters into

i

, Where the string a The number of characters to be modified is

ca = n - c1[i]

, character string b The number of characters to be modified is

cb = m - c2[i]

, The total number of modifications is

ca + cb

.

Enumerate all the characters

i

after , The minimum value of all the modifications counted is the answer .

Code ：

class Solution {
    public int minCharacters(String a, String b) {
        int n = a.length(), m = b.length(), ans = 0x3f3f3f3f;
        int[] c1 = new int[26], c2 = new int[26];
        for (char c : a.toCharArray()) c1[c - 'a']++;
        for (char c : b.toCharArray()) c2[c - 'a']++;
        for (int i = 0; i < 26 && ans != 0; i++) {
            // 3
            int ca = n - c1[i], cb = m - c2[i];
            ans = Math.min(ans, ca + cb);
            if (i == 0) continue;
            int r1 = 0, r2 = 0;
            // 1
            for (int j = i; j < 26; j++) r1 += c1[j];
            for (int j = 0; j < i; j++) r1 += c2[j];
            // 2
            for (int j = i; j < 26; j++) r2 += c2[j];
            for (int j = 0; j < i; j++) r2 += c1[j];
            ans = Math.min(ans, Math.min(r1, r2));
        }
        return ans;
    }
}

Copy

• Time complexity ： The complexity of word frequency statistics is

O(n + m)

, The complexity of the statistical answer is

O(C^2)

, among

C = 26

Is the character set size

• Spatial complexity ：

O(C)

Last

This is us. 「 Brush through LeetCode」 The first of the series No.1737 piece , The series begins with 2021/01/01, As of the start date LeetCode I have in common 1916 questions , Part of it is a locked question , We will finish all the questions without lock first .

In this series , In addition to explaining the idea of solving problems , And give the most concise code possible . If the general solution is involved, there will be corresponding code templates .

In order to facilitate the students to debug and submit code on the computer , I've built a warehouse ：https://github.com/SharingSource/LogicStack-LeetCode .

In the warehouse address , You can see the links to the series 、 The corresponding code of the series 、LeetCode Links to the original problem and other preferred solutions .