列表

详情


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

给你两个字符串 ab ,二者均由小写字母组成。一步操作中,你可以将 ab 中的 任一字符 改变为 任一小写字母

操作的最终目标是满足下列三个条件 之一

返回达成目标所需的 最少 操作数

 

示例 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" 。

 

提示:

原站题解

去查看

上次编辑到这里,代码来自缓存 点击恢复默认模板
class Solution { public: int minCharacters(string a, string 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;
    }
};

上一题