class Solution {
public:
int minCharacters(string a, string b) {
}
};
1737. 满足三条件之一需改变的最少字符数
给你两个字符串 a
和 b
,二者均由小写字母组成。一步操作中,你可以将 a
或 b
中的 任一字符 改变为 任一小写字母 。
操作的最终目标是满足下列三个条件 之一 :
a
中的 每个字母 在字母表中 严格小于 b
中的 每个字母 。b
中的 每个字母 在字母表中 严格小于 a
中的 每个字母 。a
和 b
都 由 同一个 字母组成。返回达成目标所需的 最少 操作数。
示例 1:
输入:a = "aba", b = "caa" 输出:2 解释:满足每个条件的最佳方案分别是: 1) 将 b 变为 "ccc",2 次操作,满足 a 中的每个字母都小于 b 中的每个字母; 2) 将 a 变为 "bbb" 并将 b 变为 "aaa",3 次操作,满足 b 中的每个字母都小于 a 中的每个字母; 3) 将 a 变为 "aaa" 并将 b 变为 "aaa",2 次操作,满足 a 和 b 由同一个字母组成。 最佳的方案只需要 2 次操作(满足条件 1 或者条件 3)。
示例 2:
输入:a = "dabadd", b = "cda" 输出:3 解释:满足条件 1 的最佳方案是将 b 变为 "eee" 。
提示:
1 <= a.length, b.length <= 105
a
和 b
只由小写字母组成原站题解
golang 解法, 执行用时: 8 ms, 内存消耗: 6.3 MB, 提交时间: 2023-09-23 10:29:51
func minCharacters(a string, b string) int { alen := len(a) blen := len(b) aCnt := make([]int, 26) bCnt := make([]int, 26) for _, v := range a { aCnt[v - 'a']++ } for _, v := range b { bCnt[v - 'a']++ } ret := alen + blen for i:=0; i< 25; i++ { // z 不能作为临界值 // case1 a < b caseA := 0 // case2 a > b caseB := 0 for j:=i + 1; j < 26; j++ { caseA += aCnt[j] caseB += bCnt[j] } for j:= 0; j <= i; j++ { caseA += bCnt[j] caseB += aCnt[j] } // case3 a == b caseC := alen + blen - aCnt[i] - bCnt[i] // fmt.Println(ret, caseA, caseB, caseC) ret = min(ret, caseA, caseB, caseC) } minZ := alen + blen - aCnt[25] - aCnt[25] if minZ < ret { ret = minZ } return ret } func min(arr ...int) int { ans := arr[0] for _, num := range arr { if num < ans { ans = num } } return ans }
cpp 解法, 执行用时: 48 ms, 内存消耗: 15 MB, 提交时间: 2023-09-23 10:07:53
class Solution { public: int minCharacters(string a, string b) { vector<int> acnt(26, 0); vector<int> bcnt(26, 0); int an = a.size(), bn = b.size(); for (char c : a) acnt[c-'a']++; for (char c : b) bcnt[c-'a']++; int ans = INT_MAX, asum = 0, bsum = 0; for (int i = 0; i < 25; i++) { asum += acnt[i]; bsum += bcnt[i]; ans = min(min(ans, an-acnt[i]+bn-bcnt[i]), min(an-asum+bsum, bn-bsum+asum)); } ans = min(ans, an-acnt[25]+bn-bcnt[25]); return ans; } };
java 解法, 执行用时: 5 ms, 内存消耗: 43.6 MB, 提交时间: 2023-09-23 10:07:21
class Solution { public int minCharacters(String a, String b) { int[] cnta = new int[26]; int[] cntb = new int[26]; for(char c: a.toCharArray()) cnta[c-'a']++; for(char c: b.toCharArray()) cntb[c-'a']++; int c = a.length()+b.length(); for(int i=0; i<26; i++){ c = Math.min(c, a.length()+b.length()-cnta[i]-cntb[i]); } return Math.min(Math.min(cost(cnta, cntb), cost(cntb, cnta)), c); } private int cost(int[] a, int[] b){ // a < b // 找到一个基准字母,使得 a 中所有字母小于等于该基准值,且 b 中所有字母大于该基准值 int res = 0; for(int i=1; i<=25; i++) res += a[i]; res += b[0]; int cur = res; for(int i=1; i<=24; i++){ cur = cur - a[i] + b[i]; res = Math.min(res, cur); } return res; } }
python3 解法, 执行用时: 92 ms, 内存消耗: 16.6 MB, 提交时间: 2023-09-23 10:07:03
class Solution: def minCharacters(self, a: str, b: str) -> int: from collections import Counter a_counter = Counter(a) b_counter = Counter(b) ans=float("inf") #case 1 for i in range(25): p=0 c = chr(ord("a")+i) #基准字母为c,字符串a中的字母均应<=c,字符串b中的字母均应>c。计数不符合这个条件的字符数。 for k,v in a_counter.items(): if k>c: #k因为判定条件是k>c,所以c不能取到z,range(25) p+=v for k,v in b_counter.items(): if k<=c: #k<=c, c可以取到a p+=v ans=min(ans,p) #case 2 for i in range(25): p=0 c = chr(ord("a")+i) #基准字母为c,字符串a中的字母均应>c,字符串b中的字母均应<=c。计数不符合这个条件的字符数。 for k,v in a_counter.items(): if k<=c: #k<=c, c可以取到a p+=v for k,v in b_counter.items(): if k>c: #k因为判定条件是k>c,所以c不能取到z,range(25) p+=v ans=min(ans,p) #case 3 for i in range(26): p=0 c = chr(ord("a")+i) #基准字母为c,字符串a中的字母均应==c,字符串b中的字母均应==c。计数不符合这个条件的字符数。 for k,v in a_counter.items(): if k!=c: #k!=c,所以c可以取到a也可以取到z p+=v for k,v in b_counter.items(): if k!=c: p+=v ans=min(ans,p) return ans
cpp 解法, 执行用时: 44 ms, 内存消耗: 15 MB, 提交时间: 2023-09-23 10:06:37
class Solution { public: int minCharacters(string a, string b) { int n = a.size(), m = b.size(); vector<int> va(26, 0), vb(26, 0); for(char c : a) va[c - 'a']++; for(char c : b) vb[c - 'a']++; int ret = n + m; // 第一种情况 int case1 = n + m; for(int i = 0; i < 25; i++) { // 以第 i 个字母为临界(字符a可取,b不可取) int cur = 0; for(int j = i + 1; j < 26; j++) cur += va[j]; for(int j = 0; j <= i; j++) cur += vb[j]; case1 = min(case1, cur); } ret = min(ret, case1); // 第二种情况 int case2 = n + m; for(int i = 0; i < 25; i++) { // 以第 i 个字母为临界(字符b可取,a不可取) int cur = 0; for(int j = i + 1; j < 26; j++) cur += vb[j]; for(int j = 0; j <= i; j++) cur += va[j]; case2 = min(case2, cur); } ret = min(ret, case2); // 第三种情况 int case3 = n + m; for(int i = 0; i < 26; i++) { int cur = 0; for(int j = 0; j < 26; j++) { if(j == i) continue; cur += va[j] + vb[j]; } case3 = min(case3, cur); } ret = min(ret, case3); return ret; } };