LeetCode5662. 满足三条件之一需改变的最少字符数

 1 class Solution {
 2 public:
 3     int work(vector<int>s1,vector<int>s2){
 4         //将s1中的所有字母小于s2中的所有字母
 5         //方法就是暴力枚举所有可能的分界点
 6         int res = INT_MAX;
 7         //分界点从b开始，即下标为1开始，因为s2中所有字母要严格大于s1中的
 8         for(int j = 1;j < 26;j++){
 9             int cnt = 0;
10             for(int i = j;i < 26;i++) cnt += s2[i];  //将s2中大于等于i的加和
11             for(int i = 0;i < j;i++) cnt += s1[i];  //将s1中小于i的加和
12             res = min(res,cnt);
13         }
14         return res;
15     } 
16     
17     int minCharacters(string a, string b) {
18         //存放每个字母出现的次数，用数组做哈希
19         vector<int>s1(26);
20         vector<int>s2(26);
21         for(auto c:a) s1[c-‘a‘]++;
22         for(auto c:b) s2[c-‘a‘]++;
23 
24         //满足条件三的最小操作数，核心就是暴力枚举每个可能的出现字母
25         int n = a.size(), m = b.size();
26         int res = INT_MAX;
27         for(int i = 0;i < 26;i++){
28             res = min(res,n+m-(s1[i]+s2[i]));
29         }
30         //条件一、条件二本质一样
31         return min(res,min(work(s1,s2),work(s2,s1)));
32     }
33 };