【Day 35 】2022-01-15 - 1737. 满足三条件之一需改变的最少字符数

[azl397985856]

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

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/change-minimum-characters-to-satisfy-one-of-three-conditions/

前置知识

• 计数
• 枚举

  题目描述

  
  给你两个字符串 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 只由小写字母组成

[yetfan]

思路 还是数数， a 比 b 都大，以x为界限，a改前半部分，b改后半部分 b 比 a 都大，以x为界限，b改前半部分，a改后半部分 数字相同，遍历 len a - a中的x + len b - b中的x

代码

class Solution:
    def minCharacters(self, a: str, b: str) -> int:
        ac = [0] * 26
        bc = [0] * 26

        for c in a:
            ac[ord(c)-ord("a")] += 1

        for c in b:
            bc[ord(c)-ord("a")] += 1

        asum = 0
        bsum = 0

        way1 = inf
        way2 = inf
        way3 = inf
        for i in range(25):
            # i=0 对应字母“a”
            asum += ac[i]
            bsum += bc[i]
            way1 = min(way1, asum + len(b) - bsum)
            way2 = min(way2, len(a) - asum + bsum)
            way3 = min(way3, len(a) - ac[i] + len(b) - bc[i])

        # z
        way3z = len(a) - ac[25] + len(b) - bc[25]

        return min(way1, way2, way3, way3z)

复杂度 时间 O(n) 空间 O(1)

[HondryTravis]

思路

扫描字母表

代码

/**
 * @param {string} a
 * @param {string} b
 * @return {number}
 */
var minCharacters = function(a, b) {
    let da = new Array(26).fill(0);
    let db = new Array(26).fill(0);

    for (let i in a) da[a.charCodeAt(i) - 97] ++;
    for (let i in b) db[b.charCodeAt(i) - 97] ++;

    let an = a.length, bn = b.length, asum = 0, bsum = 0, res = Number.MAX_SAFE_INTEGER;
    for (let i = 0 ; i < 25 ; i ++) {
        asum += da[i];
        bsum += db[i];
        res = Math.min(res, an + bn - da[i] - db[i], an - asum + bsum, bn - bsum + asum);
    }
    return Math.min(res, an + bn - da[25] - db[25]);
}; 

复杂度分析

时间复杂度 O(n)

空间复杂度 O(1)

[Arya-03]

class Solution:
    def minCharacters(self, a: str, b: str) -> int:
        counter1,counter2=[0]*26,[0]*26
        for c in a: counter1[ord(c)-ord('a')]+=1
        for c in b: counter2[ord(c)-ord('a')]+=1
        way1=min(sum(counter1[i:])+sum(counter2[:i]) for i in range(1,26))
        way2=min(sum(counter2[i:])+sum(counter1[:i]) for i in range(1,26))
        way3=min(len(a)+len(b)-counter1[i]-counter2[i] for i in range(26))
        return min(way1,way2,way3)

[yan0327]

思路： 抄答案今天，状态不好555

func minCharacters(a string, b string) int {
    hashA := [26]int{}
    hashB := [26]int{}
    for i := range a{
        hashA[a[i]-'a']++
    }
    for i := range b{
        hashB[b[i]-'a']++
    }
    out := len(a)+len(b)
    for i:=0;i<25;i++{
        caseA := 0
        caseB := 0
        for j:=i+1;j<26;j++{
            caseA += hashA[j]
            caseB += hashB[j]
        }
        for j:=0;j<=i;j++{
            caseA += hashB[j]
            caseB += hashA[j]
        }
        caseC := len(a)+len(b)-hashA[i]-hashB[i]
        out = min(out,caseA,caseB,caseC)
    }
    minZ := len(a)+len(b)-hashA[25]-hashB[25]
    out = min(out,minZ)
    return out
}
func min (a int, args ...int) int{
    out := a
    for _,x := range args{
        if x < out{
            out = x
        }
    }
    return out
}

时间复杂度：O（N） 空间复杂度：O（1）

[laofuWF]

# condition 3: find the letter that appear most in both string: m + n - max_count
# condition 1 a < b: iterate a pivot letter, 
#   move all letters from right of a to the left of a
#   move all letter from left of B to right of b
# condition 2 b < a: 
#   move all letters from left of a to right of a 
#   move all letters from right of b to left

# time: O(m + n)
# space: (26)

class Solution:
    def minCharacters(self, a: str, b: str) -> int:
        m = len(a)
        n = len(b)

        pre_sum_A = [0 for i in range(26)]
        pre_sum_B = [0 for i in range(26)]
        res = m + n
        counter_A = collections.defaultdict(int)
        counter_B = collections.defaultdict(int)
        total = collections.defaultdict(int)

        for letter in a:
            counter_A[letter] += 1
            total[letter] += 1
        for letter in b:
            counter_B[letter] += 1
            total[letter] += 1

        # condition 3
        res = min(res, m + n - max(total.values()))

        for i in range(26):
            pre_sum_A[i] = counter_A[chr(i + 97)] if i == 0 else pre_sum_A[i - 1] + counter_A[chr(i + 97)]
            pre_sum_B[i] = counter_B[chr(i + 97)] if i == 0 else pre_sum_B[i - 1] + counter_B[chr(i + 97)]

        # cannot set pivot at "z"
        for i in range(25):
            # condition 1 a < b: move letters on right in a, and letters on left in b
            res = min(res, m - pre_sum_A[i] + pre_sum_B[i])

            # condition 2 b < a: move letters on left in a, and letters on right in b
            res = min(res, n - pre_sum_B[i] + pre_sum_A[i])

        return res

[zhangzz2015]

思路

• 极值问题，考虑过dp。后来觉得不需要，直接计算出三种情况下的最小操作数，最后返回其中最小操作。对于方案3，只需要找到相同字母最大的数max_num，把其他字母都改成该字母，操作数为total_num - max_num。对于方案1和2，只需统计出每个字母出现次数，之后遍历 1---24。考虑把情况1, 把s1中所有字母都变a，s2中所有的字母变成比a大，该操作数 s1.size() -sum_a + sum_b; 此处sum_a 为 s1 中字母a的个数 sum_b 为字母s2 中a的个数。时间复杂度为O(n)，空间复杂度为O(1)。

关键点

代码

• 语言支持：C++

C++ Code:

class Solution {
public:
    int minCharacters(string a, string b) {
        // 
        vector<int>  record_a(26,0); 
        vector<int>  record_b(26,0);         
        int max_num_a =0; 
        int max_num_b =0; 
        int left=0;
        while(left<a.size()||left<b.size())
        {
            if(left<a.size())
            {
                int index = a[left]-'a';
                record_a[index]++; 
                max_num_a = max(max_num_a, record_a[index]);                 
            }
            if(left<b.size())
            {
                int index = b[left]-'a';
                record_b[index]++; 
                max_num_b = max(max_num_b, record_b[index]);                 
            }
            left++; 
        }
        int ret = a.size() - max_num_a + b.size() - max_num_b; 
        // loop all situation. And calculate change. and find smallest one. 
        int sum_a=record_a[0];
        int sum_b=record_b[0];          
        for(int i=1; i< 26; i++)
        {
            // Two situation. one all a < b.  The other is all a>b. 
            int change_1 = a.size() -sum_a + sum_b; 
            int change_2 = b.size() -sum_b + sum_a; 
            ret = min(ret, change_1); 
            ret = min(ret, change_2); 
            sum_a +=record_a[i]; 
            sum_b +=record_b[i]; 
        }

        return ret;        
    }
};

[falconruo]

思路: 模拟

复杂度分析:

1. 时间复杂度: O(n + m), 其中 n, m是字符串a 和 b长度
2. 空间复杂度: O(1)

代码(C++):

class Solution {
public:
    int minCharacters(string a, string b) {
        vector<int> freqA(26, 0);
        vector<int> freqB(26, 0);

        for (auto& c : a)
            freqA[c - 'a']++;

        for (auto& c : b)
            freqB[c - 'a']++;

        int res = INT_MAX;
        for (int key = 0; key < 26; key++) {
            int changes = 0;
            if (key > 0) {

                for (int j = key; j < 26; j++)
                    changes += freqA[j];

                for (int j = 0; j < key; j++)
                    changes += freqB[j];

                res = min(res, changes);
                changes = 0;

                for (int j = key; j < 26; j++)
                    changes += freqB[j];

                for (int j = 0; j < key; j++)
                    changes += freqA[j];

                res = min(res, changes);
            }
            changes = 0;

            for (int j = 0; j < 26; j++) {
                if (j != key) {
                    changes += freqA[j];
                    changes += freqB[j];
                }
            }
            res = min(res, changes);
        }

        return res;
    }
};

[wangzehan123]

代码

• 语言支持：Java

Java Code:

class Solution {
    public int minCharacters(String a, String b) {
        // 初始化数组用于存储字符串a和b中的字母；
        int[] acnt = new int[26];
        int[] bcnt = new int[26];
        // 获取a和b的字母总数；
        int an = a.length(), bn=b.length();

        // 分别对字符串的字母计数；
        for (char c: a.toCharArray()) {
            acnt[c-'a']++;
        }
        for (char c: b.toCharArray()) {
            bcnt[c-'a']++;
        }

        // 遍历两段字母表计算“最少操作数”；
        int ans = Integer.MAX_VALUE, ans_1, ans_2, asum=0, bsum=0;
        for (int i = 0; i<25; i++) {
            // 计算两段字母表的前缀和；
            asum += acnt[i];
            bsum += bcnt[i];
            // 满足条件1或条件2的操作数：操作a的字母均小于等于字母i，操作b的字母均大于字母i，或者反之；
            // 注意不能计算字母为‘z’的情况，举例字符串是"a"和"aazz"
            ans_1 = Math.min(an-asum+bsum, bn-bsum+asum);

            // 满足条件3的操作数：操作a和b中字母i以外的字母，令均转为i；
            ans_2 = Math.min(ans, an-acnt[i]+bn-bcnt[i]);

            // 贪心策略：比较保留当前的最少操作数；
            ans = Math.min(ans_1, ans_2);
        }
        // 计算条件3在字母为‘z’时的操作数，并比较；
        ans = Math.min(ans, an-acnt[25]+bn-bcnt[25]);
        return ans;
    }
}

[youzhaing]

思路：

枚举 + 计数

code

class Solution:
    def minCharacters(self, a: str, b: str) -> int:
        la = [0] * 26
        lb = [0] * 26
        for i in a:
            la[ord(i) - ord('a')] += 1
        for i in b:
            lb[ord(i) - ord('a')] += 1

        #way1:对于某个分割线，计算a中大于等于分割线的字母个数 + b中小于分割线的字母个数，再遍历25个字母(a不算）
        way1 = min(sum(la[i: ]) + sum(lb[:i]) for i in range(1, 26))
        way2 = min(sum(lb[i:]) + sum(la[:i]) for i in range(1, 26))
        way3 = min(len(a) + len(b) - la[i] - lb[i] for i in range(26))

        return min(way1, way2, way3)

复杂度：

• 时间复杂度：O(m + n), m, n是a, b字符串长度。三次遍历实际上能合成一次遍历。
• 空间复杂度：O(1)，列表是定长

[zwx0641]

class Solution { public int minCharacters(String a, String b) { int[] dictA = new int[26]; int[] dictB = new int[26];

    for (char c : a.toCharArray()) {
        dictA[c - 'a']++;
    }

    for (char c : b.toCharArray()) {
        dictB[c - 'a']++;
    }

    int tmp = 0;
    for (int i = 0; i < 26; i++) {
        tmp = Math.max(tmp, dictA[i] + dictB[i]);
    }
    int res = a.length() + b.length() - tmp;
    int ta = 0, tb = 0;
    for (int i = 25; i > 0; i--) {
        ta += dictA[i];
        tb += dictB[i];

        res = Math.min(res, Math.min(ta + b.length() - tb, tb + a.length() - ta));
    }
    return res;
}

}

[zwang2244]

思路

condition1&2: 对每一个letter a-y 算a中所有<=这个letter的数和b中所有<=这个letter的数 #operations = 把a所有letter变得比这个letter小 + 把b所有letter变得比这个letter大 = a.length() - a有多少<=这个letter + b有多少<=这个letter； 对b也是一样做，然后取两者最小值 condition3: 就是看a中哪个char frequency最高，把其他letter都变成这个frequency最高的。b中哪个char frequency最高，把其他letter都变成这个frequency最高的。两个结果加一加就是满足condition3 的 #operations。

代码

class Solution {
    public int minCharacters(String a, String b) {
        int[] counta = new int[26];
        int[] countb = new int[26];

        int max_a = 0;
        for(int i = 0; i < a.length(); i++){
            char curr_a = a.charAt(i);
            counta[curr_a - 'a']++;
            max_a = Math.max(max_a, counta[curr_a - 'a']);
        }

        int max_b = 0;
        for(int j = 0; j < b.length(); j++){
            char curr_b = b.charAt(j);
            countb[curr_b - 'a']++;
            max_b = Math.max(max_b, countb[curr_b - 'a']);
        }

        int ans = a.length() - max_a + b.length() - max_b;

        int sum_a = 0; // count the number of letters <= some letter
        int sum_b = 0; // count the number of letters <= some letter
        for(int k = 0; k < 25; k++){
            sum_a += counta[k];
            sum_b += countb[k];
            int o1 = a.length() - sum_a + sum_b; 
            int o2 = b.length() - sum_b + sum_a; 
            ans = Math.min(ans, o1);
            ans = Math.min(ans, o2);
        }

        return ans;
    }
}

复杂度分析

• 时间复杂度：O(N)，其中 N 为数组长度。
• 空间复杂度：O(1)

[CodeWithIris]

Question

Day35 1737
https://leetcode-cn.com/problems/change-minimum-characters-to-satisfy-one-of-three-conditions/

Note (Simulation)

• 看了评论区大佬解答才写出简便答案emmmmmm
• min(ans, size_a + size_b - acnt[i] - bcnt[i]): 对应条件3，将字符串a和字符串b改为一样的字符串
• min(size_a - sum_a + sum_b, size_b - sum_b + sum_a): 对应条件1和条件2，将字符串a全部改为比字符串b小的字符或者将字符串b全部改为比字符串a小的字符(选择改动次数小的作为ans)
• 对于字母'z', 则不适用于条件1和条件2，因为字母'z'已经是最大，无法将某个字符串改为比另外一个字符串小的字符串。

Solution (C++)

class Solution {
public:
    int minCharacters(string a, string b) {
        vector<int> acnt(26, 0);
        vector<int> bcnt(26, 0);
        int size_a = a.size(), size_b = b.size(), ans = INT_MAX, sum_a = 0, sum_b = 0;
        for(char t : a) ++acnt[t - 'a'];
        for(char t : b) ++bcnt[t - 'a'];
        for(int i = 0; i < 25; ++i){
            sum_a += acnt[i];
            sum_b += bcnt[i];
            ans = min(min(ans, size_a + size_b - acnt[i] - bcnt[i]), min(size_a - sum_a + sum_b, size_b - sum_b + sum_a) );
        }
        ans = min(ans, size_a + size_b - acnt[25] - bcnt[25]);
        return ans;
    }
};

Complexity

• T: O(max(size_a, size_b, 25))
• S: O(1)

[xuhzyy]

class Solution(object):
    def minCharacters(self, a, b):
        """
        :type a: str
        :type b: str
        :rtype: int
        """
        counter_A = [0] * 26
        counter_B = [0] * 26
        for c in a:
            counter_A[ord(c)-ord('a')] += 1
        for c in b:
            counter_B[ord(c)-ord('a')] += 1
        ans = len(a) + len(b)
        for i in range(26):
            ans = min(ans, len(a)+len(b)-counter_A[i]-counter_B[i])
        for i in range(1,26):
            t = 0
            for j in range(i,26):
                t += counter_A[j]
            for j in range(i):
                t += counter_B[j]
            ans = min(ans, t)
        for i in range(1,26):
            t = 0
            for j in range(i,26):
                t += counter_B[j]
            for j in range(i):
                t += counter_A[j]
            ans = min(ans, t)
        return ans

[Alexno1no2]

# 暴力破解
# 先算a、b里每个字母的counter
# 再分别计算满足情况1/2/3时，阈值分别为25/26个字母的操作步数然后求最小值。
# 再对求得的三个最小值求最小值

class Solution:
    def minCharacters(self, a: str, b: str) -> int:
        counter1,counter2=[0]*26,[0]*26
        for c in a: counter1[ord(c)-ord('a')]+=1
        for c in b: counter2[ord(c)-ord('a')]+=1
        way1=min(sum(counter1[i:])+sum(counter2[:i]) for i in range(1,26))
        way2=min(sum(counter2[i:])+sum(counter1[:i]) for i in range(1,26))
        way3=min(len(a)+len(b)-counter1[i]-counter2[i] for i in range(26))
        return min(way1,way2,way3)

[ZacheryCao]

Idea

Enumerate

Code

class Solution:
    def minCharacters(self, a: str, b: str) -> int:
        res = math.inf
        for i in range(1, 27):
            count = 0
            cur = chr(ord('a')+i)
            for j in a:
                if ord(j) >= ord(cur):
                    count += 1
            for j in b:
                if ord(j) < ord(cur):
                    count += 1
            res = min(res, count)
        count = [0]*26
        for i in a:
            count[ord(i)-ord('a')] += 1
        for i in b:
            count[ord(i)-ord('a')] += 1
        res = min(res, len(a) + len(b) - max(count))
        return res

Complexity:

Time: O(N) Space: O(N)

[Toms-BigData]

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

思路

三个条件，其中条件1和条件2是相同的，通过遍历字符串得到字母的个数值，遍历a~y（z不符合该方法）以每一个字符作为a的最大b的最小（或b的最大a的最小）找出需要变化的个数。 条件3就是两个字符穿的长度减去该字符出现的个数。

golang代码

func minCharacters(a string, b string) int {
    ans:=len(a)+len(b)
    lista:= make([]int, 26)
    listb:=make([]int,26)
    for i := 0; i < len(a); i++ {
        lista[a[i]-'a']++
    }
    for i := 0; i < len(b); i++ {
        listb[b[i]-'a']++
    }
    for i := 0; i < 25; i++ {
        numa:=0
        numb:=0
        for j := i+1; j < 26; j++ {
            numa+=lista[j]
            numb+=listb[j]
        }
        for j := 0; j <= i; j++ {
            numa+=listb[j]
            numb+=lista[j]
        }
        numc:=len(a)+len(b)-lista[i]-listb[i]
        ans = min(numa,numb,numc,ans)
    }
    minZ := len(a)+len(b)-lista[25]-listb[25]
    if minZ < ans {
        ans = minZ
    }
    return ans
}
func min(a, b, c, ans int) int {
    if a<ans{
        ans = a
    }
    if b<ans{
        ans = b
    }
    if c<ans{
        ans = c
    }
    return ans
}

复杂度

时间:O(n) 空间:O(n)

[ZJP1483469269]

class Solution:
    def minCharacters(self, a: str, b: str) -> int:
        a1,b1 = [0]*26,[0]*26
        for s in a:
            a1[ord(s) - ord('a')] += 1
        for s in b:
            b1[ord(s) - ord('a')] += 1       

        cnt1 = cnt2 = 0
        an = sum(a1)
        bn = sum(b1)
        ans = an + bn
        for i in range(25):
            cnt1 += a1[i]
            cnt2 += b1[i]

            ans = min(ans , an - cnt1 + cnt2 , bn - cnt2 + cnt1 ,an + bn - a1[i] - b1[i] )

        return min(ans,an + bn - a1[25] - b1[25])

[spacker-343]

思路

统计两个字符串的每个字符，计算变为同一个字母的结果，然后计算a严格小于b，和b严格小于a的结果。对于a严格小于b来讲，此时结果 = 把a[0, i]的所有字符提到(i, 26)区间(即preSumA) + 把b(i, 26)的所有字符提到[0, i]区间(即 n - preSumB)，因为z后面已经没字符了，不能找到一个严格小于z的字符了，所以只能遍历到24.

代码

class Solution {
    public int minCharacters(String a, String b) {
        int[] countA = new int[26];
        int[] countB = new int[26];
        for (char c : a.toCharArray()) {
            countA[c - 'a']++;
        }
        for (char c : b.toCharArray()) {
            countB[c - 'a']++;
        }
        int m = a.length();
        int n = b.length();
        int res = Integer.MAX_VALUE;
        for (int i = 0; i < 26; i++) {
            res = Math.min(res, m + n - countA[i] -  countB[i]);
        }
        int preSumA = 0;
        int preSumB = 0;
        for (int i = 0; i < 25; i++) {
            preSumA += countA[i];
            preSumB += countB[i];
            res = Math.min(res, preSumA + n - preSumB);
            res = Math.min(res, preSumB + m - preSumA);
        }
        return res;
    }
}

复杂度

时间复杂度: O(n) 空间复杂度: O(1)

[LinnSky]

思路

抄写答案

    var minCharacters = function(a, b) {
        let da = new Array(26).fill(0)
        let db = new Array(26).fill(0)
        for(let i in a) {
            da[a.charCodeAt(i) - 97]++
        }
        for(let i in b) {
            db[b.charCodeAt(i) - 97]++
        }
        let an = a.length, bn = b.length, asum = 0, bsum = 0, res = Number.MAX_SAFE_INTEGER;
        for(let i = 0; i < 25; i++) {
            asum += da[i]
            bsum += db[i]
            res = Math.min(res, an+bn-da[i]-db[i], an-asum+bsum, bn-bsum+asum)
        }
        return Math.min(res, an+bn-da[25]-db[25])
    };

[stackvoid]

思路

不会 看答案写的

代码

class Solution {
    public int minCharacters(String a, String b) {
        // 初始化数组用于存储字符串a和b中的字母；
        int[] acnt = new int[26];
        int[] bcnt = new int[26];
        // 获取a和b的字母总数；
        int an = a.length(), bn=b.length();

        // 分别对字符串的字母计数；
        for (char c: a.toCharArray()) {
            acnt[c-'a']++;
        }
        for (char c: b.toCharArray()) {
            bcnt[c-'a']++;
        }

        // 遍历两段字母表计算“最少操作数”；
        int ans = Integer.MAX_VALUE, ans_1, ans_2, asum=0, bsum=0;
        for (int i = 0; i<25; i++) {
            // 计算两段字母表的前缀和；
            asum += acnt[i];
            bsum += bcnt[i];
            // 满足条件1或条件2的操作数：操作a的字母均小于等于字母i，操作b的字母均大于字母i，或者反之；
            // 注意不能计算字母为‘z’的情况，举例字符串是"a"和"aazz"
            ans_1 = Math.min(an-asum+bsum, bn-bsum+asum);

            // 满足条件3的操作数：操作a和b中字母i以外的字母，令均转为i；
            ans_2 = Math.min(ans, an-acnt[i]+bn-bcnt[i]);

            // 贪心策略：比较保留当前的最少操作数；
            ans = Math.min(ans_1, ans_2);
        }
        // 计算条件3在字母为‘z’时的操作数，并比较；
        ans = Math.min(ans, an-acnt[25]+bn-bcnt[25]);
        return ans;
    }
}

复杂度分析

时间复杂度O(N) 空间复杂度O(1)

[didiyang4759]

参考解析

class Solution:
    def minCharacters(self, a: str, b: str) -> int:
        counter1,counter2=[0]*26,[0]*26
        for c in a: counter1[ord(c)-ord('a')]+=1
        for c in b: counter2[ord(c)-ord('a')]+=1
        way1=min(sum(counter1[i:])+sum(counter2[:i]) for i in range(1,26))
        way2=min(sum(counter2[i:])+sum(counter1[:i]) for i in range(1,26))
        way3=min(len(a)+len(b)-counter1[i]-counter2[i] for i in range(26))
        return min(way1,way2,way3)

时间复杂度O(1)

[cszys888]

class Solution:
    def minCharacters(self, a: str, b: str) -> int:
        counter1 = [0]*26
        counter2 = [0]*26
        for c in a:
            counter1[ord(c) - ord('a')] += 1
        for c in b:
            counter2[ord(c) - ord('a')] += 1

        solution1 = min([sum(counter1[i:])+sum(counter2[:i]) for i in range(1,26)])
        solution2 = min([sum(counter1[:i])+sum(counter2[i:]) for i in range(1,26)])
        solution3 = min([len(a)+len(b) - counter1[i] - counter2[i] for i in range(26)])

        return min(solution1, solution2, solution3)

time complexity: O(N+M) where N and M stand for the length of a and b space complexity: O(1)

[CoreJa]

思路

• 朴素枚举+哈希：核心点是枚举字母a-z，令其为x，计算使字符串a完全小于x并使字符串b完全大于等于x所需要的操作数就能找到满足条件1的最小操作数，条件2完全对称，条件3直接统计可得。
• 朴素枚举：将哈希替换成了列表，企图加快速度，然而在LC上速度更慢

• 枚举+动规：朴素枚举的问题在于重复计算，拿满足条件1的情况举例，枚举字母x为a的结果，与x为b的结果之间是存在联系的，x=a的结果只需要再-A[i]+B[i](i为x=b时的下标)，就能得到x为b的结果。本质和上面的朴素枚举是同理的。

  代码

  class Solution:
  # 朴素枚举+哈希：核心点是枚举字母`a`-`z`，令其为`x`，计算使字符串`a`完全小于`x`并使字符串`b`完全
  # 大于等于`x`所需要的操作数就能找到满足条件1的最小操作数，条件2完全对称，条件3直接统计可得。
  def minCharacters1(self, a: str, b: str) -> int:
      cnt_a = Counter(a)
      cnt_b = Counter(b)
      cnt_total = Counter(a + b)
  
      def solve(cnt_a, cnt_b):
          ans = float('inf')
          for i in range(1, 26):
              t = 0
              for j in range(i, 26):
                  t += cnt_a[chr(97 + j)]
              for j in range(i):
                  t += cnt_b[chr(97 + j)]
              ans = min(ans, t)
          return ans
  
      return min(solve(cnt_a, cnt_b), solve(cnt_b, cnt_a), len(a) + len(b) - cnt_total.most_common(1)[0][1])
  
  # 朴素枚举：将哈希替换成了列表，企图加快速度，然而在LC上速度更慢
  def minCharacters2(self, a: str, b: str) -> int:
      cnt_a = [0] * 26
      cnt_b = [0] * 26
      cnt_total = [0] * 26
      for ch in a:
          cnt_a[ord(ch) - 97] += 1
      for ch in b:
          cnt_b[ord(ch) - 97] += 1
      for i in range(26):
          cnt_total[i] = cnt_a[i] + cnt_b[i]
  
      def solve(cnt_a, cnt_b):
          ans = float('inf')
          for i in range(1, 26):
              t = 0
              for j in range(i, 26):
                  t += cnt_a[j]
              for j in range(i):
                  t += cnt_b[j]
              ans = min(ans, t)
          return ans
  
      return min(solve(cnt_a, cnt_b), solve(cnt_b, cnt_a), len(a) + len(b) - max(cnt_total))
  
  # 枚举+动规：朴素枚举的问题在于重复计算，拿满足条件1的情况举例，枚举字母`x`为`a`的结果，
  # 与`x`为`b`的结果之间是存在联系的，`x=a`的结果只需要再`-A[i]+B[i]`(`i`为x=b时的下标)，
  # 就能得到`x`为b的结果。本质和上面的朴素枚举是同理的。
  def minCharacters(self, a: str, b: str) -> int:
      m, n = len(a), len(b)
      A = [*map(a.count, ascii_lowercase)]
      B = [*map(b.count, ascii_lowercase)]
      result, p = m + n, [m, n]
      for i in range(25):
          p[0] -= A[i] - B[i]
          p[1] -= B[i] - A[i]
          result = min(result, m + n - A[i] - B[i], p[0], p[1])
      return min(result, m + n - A[-1] - B[-1])

[JuliaShiweiHuang]

""" class Solution: def minCharacters(self, a: str, b: str) -> int: ac = [0] 26 bc = [0] 26

    for c in a:
        ac[ord(c)-ord("a")] += 1

    for c in b:
        bc[ord(c)-ord("a")] += 1

    asum = 0
    bsum = 0

    way1 = inf
    way2 = inf
    way3 = inf
    for i in range(25):
        # i=0 对应字母“a”
        asum += ac[i]
        bsum += bc[i]
        way1 = min(way1, asum + len(b) - bsum)
        way2 = min(way2, len(a) - asum + bsum)
        way3 = min(way3, len(a) - ac[i] + len(b) - bc[i])

    # z
    way3z = len(a) - ac[25] + len(b) - bc[25]

    return min(way1, way2, way3, way3z)

"""

[zwmanman]

class Solution: def minCharacters(self, A: str, B: str) -> int: counter_A = [0] 26 counter_B = [0] 26 for a in A: counter_A[ord(a) - ord('a')] += 1 for b in B: counter_B[ord(b) - ord('a')] += 1 ans = len(A) + len(B) for i in range(26): ans = min(ans, len(A) + len(B) - counter_A[i] - counter_B[i]) for i in range(1, 26): t = 0 for j in range(i, 26): t += counter_A[j] for j in range(i): t += counter_B[j] ans = min(ans, t) for i in range(1, 26): t = 0 for j in range(i, 26): t += counter_B[j] for j in range(i): t += counter_A[j] ans = min(ans, t) return ans

[gaoyi86]

思路 不会 看答案写的

代码 class Solution { public int minCharacters(String a, String b) { // 初始化数组用于存储字符串a和b中的字母； int[] acnt = new int[26]; int[] bcnt = new int[26]; // 获取a和b的字母总数； int an = a.length(), bn=b.length();

    // 分别对字符串的字母计数；
    for (char c: a.toCharArray()) {
        acnt[c-'a']++;
    }
    for (char c: b.toCharArray()) {
        bcnt[c-'a']++;
    }

    // 遍历两段字母表计算“最少操作数”；
    int ans = Integer.MAX_VALUE, ans_1, ans_2, asum=0, bsum=0;
    for (int i = 0; i<25; i++) {
        // 计算两段字母表的前缀和；
        asum += acnt[i];
        bsum += bcnt[i];
        // 满足条件1或条件2的操作数：操作a的字母均小于等于字母i，操作b的字母均大于字母i，或者反之；
        // 注意不能计算字母为‘z’的情况，举例字符串是"a"和"aazz"
        ans_1 = Math.min(an-asum+bsum, bn-bsum+asum);

        // 满足条件3的操作数：操作a和b中字母i以外的字母，令均转为i；
        ans_2 = Math.min(ans, an-acnt[i]+bn-bcnt[i]);

        // 贪心策略：比较保留当前的最少操作数；
        ans = Math.min(ans_1, ans_2);
    }
    // 计算条件3在字母为‘z’时的操作数，并比较；
    ans = Math.min(ans, an-acnt[25]+bn-bcnt[25]);
    return ans;
}

} 复杂度分析 时间复杂度O(N) 空间复杂度O(1)

[yijing-wu]

代码

class Solution {
    public int minCharacters(String a, String b) {
        int[] acnt = new int[26];
        int[] bcnt = new int[26];
        int an = a.length(), bn=b.length();

        for (char c: a.toCharArray()) {
            acnt[c-'a']++;
        }
        for (char c: b.toCharArray()) {
            bcnt[c-'a']++;
        }

        int ans = Integer.MAX_VALUE, ans_1, ans_2, asum=0, bsum=0;
        for (int i = 0; i<25; i++) {
            // 计算前缀和
            asum += acnt[i];
            bsum += bcnt[i];
            ans_1 = Math.min(an-asum+bsum, bn-bsum+asum);
            ans_2 = Math.min(ans, an-acnt[i]+bn-bcnt[i]);
            ans = Math.min(ans_1, ans_2);
        }
        ans = Math.min(ans, an-acnt[25]+bn-bcnt[25]);
        return ans;
    }
}

[haixiaolu]

思路

没有， 抄答案

代码/python

class Solution:
    def minCharacters(self, A: str, B: str) -> int:
        count_A = [0] * 26
        count_B = [0] * 26
        for a in A:
            count_A[ord(a) - ord('a')] += 1
        for b in B:
            count_B[ord(b) - ord('a')] += 1
        ans = len(A) + len(B)
        for i in range(26):
            ans = min(ans, len(A) + len(B) - count_A[i] - count_B[i])

        # 枚举A的最大字母
        for i in range(1, 26):
            t = 0
            # A中 大于等于i的所有字符进行一次操作
            for j in range(i, 26):
                t += count_A[j]
            # B 中大于等于i的所有字符进行一次操作
            for j in range(i):
                t += count_B[j]
            # 枚举所有情况取最小的
            ans = min(ans, t)
        for i in range(1, 26):
            t = 0
            for j in range(i, 26):
                t += count_B[j]
            for j in range(i):
                t += count_A[j]
            ans = min(ans, t)
        return ans

复杂度分析：

• 时间复杂度： O(m + n)
• 空间复杂度： O(1)

[jiaqiliu37]

class Solution:
    def minCharacters(self, a: str, b: str) -> int:
        countA = [0]*26
        countB = [0]*26
        for letter in a:
            countA[ord(letter) - ord('a')] += 1
        for letter in b:
            countB[ord(letter) - ord('a')] += 1
        ans = len(a) + len(b)
        for i in range(26):
            ans = min(ans, len(a) + len(b) - countA[i] - countB[i])
        for i in range(1, 26):
            t = 0
            for j in range(i, 26):
                t += countA[j]
            for j in range(i):
                t += countB[j]
            ans = min(ans, t)
        for i in range(1, 26):
            t = 0
            for j in range(i, 26):
                t += countB[j]
            for j in range(i):
                t += countA[j]
            ans = min(ans, t)

        return ans
``` Time complexity O(len(a)+len(b))
Space complexity O(26)

[rzhao010]

Thoughts Turning letters into count array

Code

    public int minCharacters(String a, String b) {
        // count letters in a and b
        int[] acnt = new int[26];
        int[] bcnt = new int[26];

        int an = a.length(), bn = b.length();

        for (char c: a.toCharArray()) {
            acnt[c - 'a']++;
        }
        for (char c: b.toCharArray()) {
            bcnt[c - 'a']++;
        }

        // traverse two cnt to calculate the minimum ops
        int ans = Integer.MAX_VALUE, ans_1, ans_2, asum = 0, bsum = 0;
        for (int i = 0; i < 25; i++) {
            asum += acnt[i];
            bsum += bcnt[i];
            // # of operations to meet 1 or 2:
            // make letters in 'a' less than i, letters in 'b' greater than i 
            ans_1 = Math.min(an - asum + bsum, bn - bsum + asum);

            // # of operations to meet 3:
            // turn all letters beside 'i' itself into 'i'
            ans_2 = Math.min(ans, an - acnt[i] + bn - bcnt[i]);

            ans = Math.min(ans_1, ans_2);
        }

        // the case of all 'z'
        ans = Math.min(ans, an - acnt[25] + bn - bcnt[25]);
        return ans;
    }

Complexity Time: O(n), length of a or b Space: O(n), count arrays

[wenjialu]

thought

求出各个字母出现的频次之后只需扫一遍字母表就能得出解了。

code

class Solution:
    def minCharacters(self, a: str, b: str) -> int:
        # a < b; or b < a or only 1 char.
             s1, s2 = [0] * 26, [0] * 26
        for c in a:
            s1[ord(c) - ord('a')] += 1
        for c in b:
            s2[ord(c) - ord('a')] += 1

        l1, l2 = len(a), len(b)
        cnt1, cnt2, ans = 0, 0, sys.maxsize
        for i in range(25):
            cnt1 += s1[i]
            cnt2 += s2[i]
            ans = min(ans, l1 + l2 - s1[i] - s2[i], l1 - cnt1 + cnt2, l2 - cnt2 + cnt1)
        return min(ans, l1 + l2 - s1[25] - s2[25])

com

Time O(n) Space O(n)

[junbuer]

思路

• 前缀和计数

代码

class Solution(object):
    def minCharacters(self, a, b):
        """
        :type a: str
        :type b: str
        :rtype: int
        """ 
        m = len(a)
        n = len(b)
        acnt = [0] * 26
        bcnt = [0] * 26
        for ch in a:
            acnt[ord(ch) - 97] += 1
        for ch in b:
            bcnt[ord(ch) - 97] += 1

        asum, bsum = 0, 0
        ans = float("inf")

        for i in range(25):
            asum += acnt[i]
            bsum += bcnt[i]
            ans = min(min(ans, m + n - acnt[i] - bcnt[i]), m - asum + bsum, n - bsum + asum)

        ans = min(ans, m + n - acnt[25] - bcnt[25])
        return ans 

复杂度分析

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$

[Serena9]

代码

class Solution:
    def minCharacters(self, A: str, B: str) -> int:
        ca = collections.Counter(A)
        cb = collections.Counter(B)
        # ca 中严格大于 cb 的最小操作数
        def greater_cost(ca, cb):
            ans = float("inf")
            # 枚举 ca 中的最小值
            for i in range(1, 26):
                count = 0
                # 将 ca 中小于最小值的都进行一次操作
                for j in range(i):
                    count += ca[chr(97 + j)]
                # 将 cb 中大于等于最小值的都进行一次操作（注意这里的等号）
                for j in range(i, 26):
                    count += cb[chr(97 + j)]
                ans = min(ans, count)
            return ans

        def equal_cost(ca, cb):
            ans = float("inf")
            for i in range(26):
                ans = min(ans, len(A) + len(B) - ca[chr(97 + i)] - cb[chr(97 + i)])
            return ans

        return min(greater_cost(ca, cb), greater_cost(cb, ca), equal_cost(ca, cb))

[Bochengwan]

思路

对三种情况分别计算，然后return最小的

代码

class Solution:
    def minCharacters(self, a: str, b: str) -> int:
        n = len(a)
        m = len(b)

        a_counter = collections.defaultdict(int)

        b_counter = collections.defaultdict(int)

        for e in a:
            a_counter[e]+=1
        for e in b:
            b_counter[e]+=1

        a1 = a2 = a3 = float('inf')
        c11 = n
        c21 = m
        c12 = c22 = 0

        for i in range(26):

            separator = chr(ord('a')+i)
            c3 = n-a_counter[separator]+m-b_counter[separator]
            a3 = min(a3,c3)

            if separator in ['a']:
                continue

            else:               
                c11-=a_counter[chr(ord('a')+i-1)]
                c12+=b_counter[chr(ord('a')+i-1)]
                c21-=b_counter[chr(ord('a')+i-1)]
                c22+=a_counter[chr(ord('a')+i-1)]

                c1 = c11+c12
                c2 = c21+c22

                a1 = min(a1,c1)
                a2 = min(a2,c2)

        return min(a1,a2,a3)

复杂度分析

• 时间复杂度：O(N)，其中 N 为数组长度。
• 空间复杂度：O(N)

[hdyhdy]

思路： 枚举比对最小值。 https://leetcode-solution.cn/solutionDetail?type=3&id=35&max_id=2

func minCharacters(a string, b string) int {
    hashA := [26]int{}
    hashB := [26]int{}
    for i := range a{
        hashA[a[i]-'a']++
    }
    for i := range b{
        hashB[b[i]-'a']++
    }
    out := len(a)+len(b)
    for i:=0;i<25;i++{
        caseA := 0
        caseB := 0
        for j:=i+1;j<26;j++{
            caseA += hashA[j]
            caseB += hashB[j]
        }
        for j:=0;j<=i;j++{
            caseA += hashB[j]
            caseB += hashA[j]
        }
        caseC := len(a)+len(b)-hashA[i]-hashB[i]
        out = min(out,caseA,caseB,caseC)
    }
    minZ := len(a)+len(b)-hashA[25]-hashB[25]
    out = min(out,minZ)
    return out
}
func min (a int, args ...int) int{
    out := a
    for _,x := range args{
        if x < out{
            out = x
        }
    }
    return out
}

时间复杂度：O(m + n)

空间复杂度：O(26)

[LannyX]

代码

class Solution {
    public int minCharacters(String a, String b) {
        int[] countA = new int[26];
        int[] countB = new int[26];
        int lenA = a.length(), lenB = b.length();
        int ans = Integer.MAX_VALUE, ansA, ansB, sumA = 0, sumB = 0;

        for(char c : a.toCharArray()){
            countA[c - 'a']++;
        }
        for(char c : b.toCharArray()){
            countB[c - 'a']++;
        }
        for(int i = 0; i < 25; i++){
            sumA += countA[i];
            sumB += countB[i];

            ansA = Math.min(lenA - sumA + sumB, lenB - sumB + sumA);
            ansB = Math.min(ans, lenA - countA[i] + lenB - countB[i]);
            ans = Math.min(ansA, ansB);
        }
        ans = Math.min(ans, lenA - countA[25] + lenB - countB[25]);
        return ans;
    }
}

复杂度分析

• 时间复杂度：O(m+n)
• 空间复杂度：O(1)

[zhiyuanpeng]

class Solution:
    def minCharacters(self, A: str, B: str) -> int:
        counter_A = [0] * 26
        counter_B = [0] * 26
        for a in A:
            counter_A[ord(a) - ord('a')] += 1
        for b in B:
            counter_B[ord(b) - ord('a')] += 1
        ans = len(A) + len(B)
        for i in range(26):
            ans = min(ans, len(A) + len(B) - counter_A[i] - counter_B[i])
        for i in range(1, 26):
            t = 0
            for j in range(i, 26):
                t += counter_A[j]
            for j in range(i):
                t += counter_B[j]
            ans = min(ans, t)
        for i in range(1, 26):
            t = 0
            for j in range(i, 26):
                t += counter_B[j]
            for j in range(i):
                t += counter_A[j]
            ans = min(ans, t)
        return ans

[li65943930]

class Solution: def minCharacters(self, A: str, B: str) -> int: ca = collections.Counter(A) cb = collections.Counter(B)

ca 中严格大于 cb 的最小操作数

    def greater_cost(ca, cb):
        ans = float("inf")
        # 枚举 ca 中的最小值
        for i in range(1, 26):
            count = 0
            # 将 ca 中小于最小值的都进行一次操作
            for j in range(i):
                count += ca[chr(97 + j)]
            # 将 cb 中大于等于最小值的都进行一次操作（注意这里的等号）
            for j in range(i, 26):
                count += cb[chr(97 + j)]
            ans = min(ans, count)
        return ans

    def equal_cost(ca, cb):
        ans = float("inf")
        for i in range(26):
            ans = min(ans, len(A) + len(B) - ca[chr(97 + i)] - cb[chr(97 + i)])
        return ans

    return min(greater_cost(ca, cb), greater_cost(cb, ca), equal_cost(ca, cb))

[ginnydyy]

Problem

https://leetcode.com/problems/change-minimum-characters-to-satisfy-one-of-three-conditions/

Notes

• Simulation
• Solution reference: https://leetcode.com/problems/change-minimum-characters-to-satisfy-one-of-three-conditions/discuss/1032042/Java-Detailed-Explanation-Find-the-Boundary-Letter.
• To meet condition 1/2 is to find a boundary letter, where all the characters of string a is < boundary, and all the characters of string b is >= boundary.
  • Since no character can be < 'a', so the boundary candidates are from 'b' to 'z', 25 candidates.
  • For each boundary candidate, iterate each character of string a and string b, to count the number of conversion to meet the requirement. Then maintain the min value for each boundary candidate.
  • Return the min value as the result to make string a and string b meet the condition 1/2.
• To meet condition 3 is to count the max appearing time of a letter in both string a and string b, then to convert other characters of string a and b into a distinct letter.
  • Can use a 26 long int array to count each letter's appearing time.
  • Since the problem only asks for the count, the index doesn't matter, so can sort the array to find out the max appearing time.
  • The min conversion time is a.length() + b.length() - max appearing time.
• The final min operation count is the min of operations of meeting condition 1/2/3.

Solution

class Solution {
    public int minCharacters(String a, String b) {
        int count1 = helper1(a, b);
        int count2 = helper1(b, a);
        int count3 = helper2(a, b);
        return Math.min(Math.min(count1, count2), count3);
    }

    // return min times to make a strictly less than b
    private int helper1(String a, String b){
        int min = Integer.MAX_VALUE;
        // for each boundary character, to meet the requirement of a is strictly less than b,
        // all the a characters must < boundary, and all the b characters must >= boundary
        // only consider boundaries from 'b' to 'z', 25 boundary candidates 
        // because no character can be strictly less than 'a'
        for(int i = 0; i < 25; i++){
            char boundary = (char)('b' + i);
            int count = 0;
            for(char c: a.toCharArray()){
                if(boundary - c <= 0){
                    count++;
                }
            }
            for(char c: b.toCharArray()){
                if(boundary - c > 0){
                    count++;
                }
            }
            min = Math.min(min, count);
        }
        return min;
    }

    // return min times to make a and b to have only one distinct letter
    // find the max appearing time of one letter
    // the min times to make a and b to have only one distinct letter is to convert
    // other letters except that letter in a and b to one distinct letter
    private int helper2(String a, String b){
        int[] letterCount = new int[26];
        for(char c: a.toCharArray()){
            letterCount[c - 'a']++;
        }
        for(char c: b.toCharArray()){
            letterCount[c - 'a']++;
        }

        Arrays.sort(letterCount);
        int maxCount = letterCount[25];

        return a.length() + b.length() - maxCount;
    }
}

Complexity

• Time: O(m + n) (m is the length of string a, n is the length of string b).
• Space: O(1) for the int array to count letter appearing times.

[tongxw]

思路

计数 + 对26个字母模拟三个条件取最小值

class Solution {
    public int minCharacters(String a, String b) {
        // count all the letters from a and b
        int[] countA = new int[26];
        int[] countB = new int[26];
        for (char c : a.toCharArray()) {
            countA[c - 'a'] += 1;
        }
        for (char c : b.toCharArray()) {
            countB[c - 'a'] += 1;
        }

        int ans = Integer.MAX_VALUE;
        for (int k=0; k<26; k++) {
            int counter = 0;
            if (k > 0) {
                // case1, max(a) < min(b)
                // counter = 0;
                // for (int i=k; i<26; i++) { // if x in a >= k, change it to k
                //     counter += countA[i];
                // }
                // for (int i=0; i<k; i++) { // if x in b < k, change it to k+ 1
                //     counter += countB[i];
                // }
                ans = Math.min(ans, getChanges(countA, countB, k));

                // case2, max(b) < min(a), same as case 1
                // counter = 0;
                // for (int i=k; i<26; i++) { 
                //     counter += countB[i];
                // }
                // for (int i=0; i<k; i++) { 
                //     counter += countA[i];
                // }
                // ans = getChanges(countB, countA, k);
                ans = Math.min(ans, getChanges(countB, countA, k));
            }

            // case3, change every letter to k
            counter = 0;
            for (int i=0; i<26; i++) {
                if (i != k) {
                    counter += countA[i];
                    counter += countB[i];
                }
            }

            ans = Math.min(ans, counter);

            // System.out.println("idx: " + k + " ans: " + ans);
        }

        return ans;
    }

    private int getChanges(int[] countA, int[] countB, int k) {
        if (k == 0) {
            return Integer.MAX_VALUE;
        }

        int counter = 0;
        for (int i=k; i<26; i++) { // if x in a >= k, change it to k
            counter += countA[i];
        }
        for (int i=0; i<k; i++) { // if x in b < k, change it to k+ 1
            counter += countB[i];
        }
        return counter;
    }
}

SC: O(m+n) 计数 TC: O(1)

[feifan-bai]

思路

1. 条件1和条件2等价，对应greater_cost(a, b)
2. 条件3对应equal_cost(a, b)
3. 用长度为26的数组计数模拟修改字母的情况（一共只有26种字母修改可能）

代码

class Solution:
    def minCharacters(self, a: str, b: str) -> int:
        ca = collections.Counter(a)
        cb = collections.Counter(b)
        # ca 中严格大于 cb 的最小操作数
        def greater_cost(ca, cb):
            ans = float('inf')
            for i in range(1, 26):
                count = 0
                # 将 ca 中小于最小值的都进行一次操作
                for j in range(i):
                    count += ca[chr(97 + j)]
                # 将 cb 中大于等于最小值的都进行一次操作
                for j in range(i, 26):
                    count += cb[chr(97 + j)]
                ans = min(ans, count)
            return ans

        def equal_cost(ca, cb):
            ans = float("inf")
            for i in range(26):
                ans = min(ans, len(a) + len(b) - ca[chr(97 + i)] - cb[chr(97 + i)])
            return ans
        return min(greater_cost(ca, cb), greater_cost(cb, ca), equal_cost(ca, cb))

复杂度分析

• 时间复杂度：O(len(a)+len(b))
• 空间复杂度：O(26)

[Alfie100]

LeetCode题目连接： 1737. 满足三条件之一需改变的最少字符数https://leetcode-cn.com/problems/change-minimum-characters-to-satisfy-one-of-three-conditions/

解题思路

1. 构建两个哈希表A和B，分别统计26个小写字母在字符串a和b中出现的次数；
2. 然后遍历前25个字母，以位置i的字母为据点，判断如何变换a和b以达成 条件1-3，并记录每个过程所需要的最少操作次数：
   • 条件1：a中的元素均小于b中的元素：将 a中[i]位置之后 的元素全部改为 [i]位置及之前 的字符，并将 b中[i]位置及之前 的元素全部改为 [i]位置之后 的字符。此时，所需操作数为： $\big(len(a)-sum(A[:i+1])\big) + sum(B[:i+1])$；
   • 条件2：b中的元素均小于a中的元素（同上，反过来算即可）：将 a中[i]位置及之前 的元素全部改为 [i]位置之后 的字符，并将 b中[i]位置之后 的元素全部改为 [i]位置及之前 的字符 此时，所需操作数为： $sum(A[:i+1]) + \big(len(b)-(sum(B[:i+1]))$；
   • 条件3：a和b中的元素相同：将a中的元素全部变成 a中[i]位置 的元素，将b中的元素全部变成 b中[i]位置 的元素。此时，所需操作为：$\big(len(a)-A[i]\big) + \big(len(b)-B[i]\big)$。
3. 对于最后一个小写字母 'z' 只需判断条件3。

代码给出了较为详细的注释和解释。

代码

class Solution:
    def minCharacters(self, a: str, b: str) -> int:

        A = [0] * 26    # A和B分别存储字符串a和b中每个字母（26个）出现的次数
        B = [0] * 26
        for ch in a:    
            A[ord(ch)-ord('a')] += 1
        for ch in b:    
            B[ord(ch)-ord('a')] += 1

        n1, n2 = len(a), len(b)
        presum1 = presum2 = 0
        ans = n1+n2     # 初始为一个较大值即可

        # 遍历26个字母（最后一个字母'z'除外），利用前缀和求解
        for i in range(25):     # 26个小写字母中不存在大于 'z' 的字符，因此对于 'z' 需做特殊处理

            presum1 += A[i]     # 前 i+1 个字母（从'a'开始算起）出现的总次数
            presum2 += B[i]

            # 1. a中的元素均小于b中的元素：
            # 将 a中[i]位置之后 的元素全部改为 a中[i]位置及之前 的字符，并将 b中[i]位置及之前 的元素全部改为 b中[i]位置之后 的字符
            # 此时，所需操作数为： (n1-presum1) + presum2
            ans = min(ans, n1-presum1+presum2)

            # 2. b中的元素均小于a中的元素；同上，反过来算即可：
            # 将 a中[i]位置及之前 的元素全部改为 a中[i]位置之后 的字符，并将 b中[i]位置之后 的元素全部改为 b中[i]位置及之前 的字符
            # 此时，所需操作数为： presum1 + (n2-presum2)
            ans = min(ans, presum1+n2-presum2)

            # 3. a和b中的元素相同
            # 将a中的元素全部变成a中[i]位置的元素，将b中的元素全部变成b中[i]位置的元素
            # 此时，所需操作为：(n1-A[i]) + (n2-B[i])
            ans = min(ans, n1-A[i] + n2-B[i])

            # 1-3 综合可写为：
            # ans = min(ans, n1-presum1+presum2, presum1+n2-presum2, n1-A[i] + n2-B[i])

            # # i 位置之后的字符在a和b中不存在，直接返回结果
            # if presum1 == n1 and presum2 == n2:
            #     return ans

        # 对于 位置[i=25]，即表示字母'z'，不存在比'z'更大的字符
        # 因此，若字符串a或b中存在'z'，条件1-2不再判断，只需判断条件3：
        # 此时，a和b中所有字符变为'z'，需要的操作次数为：n1-A[i] + n2-B[i], i=25
        ans = min(ans, n1-A[25] + n2-B[25])

        return ans

复杂度分析

• 时间复杂度：O(n+m+k)，n和m分别为字符串a和b的长度，k=26表示26个小写字母。
• 空间复杂度：O(k)。

[alongchong]

class Solution {
    public int minCharacters(String a, String b) {
        int[] acnt = new int[26];
        int[] bcnt = new int[26];
        int an = a.length(), bn = b.length();

        for (int i = 0; i < an; i++) {
            char c = a.charAt(i);
            acnt[c - 'a']++;
        }
        for (int i = 0; i < bn; i++) {
            char c = b.charAt(i);
            bcnt[c - 'a']++;
        }
        int ans = Integer.MAX_VALUE, asum = 0, bsum = 0;
        for (int i = 0; i < 25; i++) {
            asum += acnt[i];
            bsum += bcnt[i];
            ans = Math.min(Math.min(ans, an - acnt[i] + bn - bcnt[i]), Math.min(an - asum + bsum, bn - bsum + asum));
        }
        ans = Math.min(ans, an - acnt[25] + bn - bcnt[25]);

        return ans;
    }
}

[1149004121]

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

思路

①假设a中字母最大为x，则B中字母最小为x+1.②同理③假设相同字母为x，则将所有非相同字母修改。

代码

    var minCharacters = function(A, B) {
        let countA = new Array(26).fill(0);
        let countB = new Array(26).fill(0);
        const lenA = A.length;
        const LenB = B.length;
        let ans = 100000;
        for(let a of A){
            countA[a.charCodeAt() - "a".charCodeAt()]++;
        };
        for(let b of B){
            countB[b.charCodeAt() - "a".charCodeAt()]++;
        };
        for(let i = 0; i < 26; i++){
            ans = Math.min(ans, lenA - countA[i] + LenB - countB[i]);
        };
        for(let i = 1; i < 26; i++){
            let t = 0;
            for(let j = i; j < 26; j++){
                t += countA[j];
            };
            for(let j = 0; j < i; j++){
                t += countB[j];
            };
            ans = Math.min(ans, t);
        };
        for(let i = 1; i < 26; i++){
            let t = 0;
            for(let j = i; j < 26; j++){
                t += countB[j];
            };
            for(let j = 0; j < i; j++){
                t += countA[j];
            };
            ans = Math.min(ans, t);
        };
        return ans;
    };

复杂度分析

• 时间复杂度：Max(M,N),M为字符串A长度，N为字符串B长度。
• 空间复杂度：O(1)。

[Myleswork]

思路

究极枚举

代码

class Solution {
public:

    int minCharacters(string a, string b) {
        unordered_map<char,int> ahash;
        unordered_map<char,int> bhash;
        for(char i:a) ahash[i]++;
        for(char i:b) bhash[i]++;
        int res = INT_MAX;
        for(char i='a';i<='z';i++) res = min(res,(int)a.length()+(int)b.length()-ahash[i]-bhash[i]);
        for(char i='b';i<='z';i++){ //满足条件1
            int t = 0;
            for(char a=i;a<='z';a++) t+=ahash[a];
            for(char a='a';a<i;a++) t+=bhash[a];
            res = min(res,t);
        }
        for(char i='b';i<='z';i++){ //满足条件2
            int t = 0;
            for(char a=i;a<='z';a++) t+=bhash[a];
            for(char a='a';a<i;a++) t+=ahash[a];
            res = min(res,t);
        }
        return res;
    }
};

复杂度分析

时间复杂度：O(n)

空间复杂度：O(n)

[Moin-Jer]

思路

---

枚举

代码

---

class Solution {
    public int minCharacters(String a, String b) {
        int[] arrA=new int[26];
        int[] arrB=new int[26];
        for (int i = 0; i < a.length(); i++) {
            arrA[a.charAt(i)-'a']++;
        }
        for (int i = 0; i < b.length(); i++) {
            arrB[b.charAt(i)-'a']++;
        }
        int left=b.length();
        int right=a.length();
        int min=b.length();
        for (int i = 0; i < 25; i++) {
            left+=arrA[i];
            left-=arrB[i];
            right+=arrB[i];
            right-=arrA[i];
            min=Math.min(min, Math.min(left, right));
        }
        int max=0;
        for (int i = 0; i < 26; i++) {
            max=Math.max(max, arrA[i]+arrB[i]);
        }
        return Math.min(min,a.length()+b.length()-max);
    }
}

复杂度分析

---

• 时间复杂度：O(m + n), m, n 分别为数组 A 和数组 B 的长度
• 空间复杂度：O(1)

[kbfx1234]

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

// 暴力 cpp
class Solution {
public:
    int minCharacters(string a, string b) {
        vector<int> cnt_a(26,0);
        vector<int> cnt_b(26,0);
        int lena = a.size(), lenb = b.size();

        for (auto & i : a) {
            cnt_a[i-'a']++;
        }
        for (auto & i : b) {
            cnt_b[i-'a']++;
        }

        int res = INT_MAX, asum = 0, bsum = 0;
        for (int i = 0; i < 25; ++i) {
            asum += cnt_a[i];
            bsum += cnt_b[i];

            res = min(min(res, lena - cnt_a[i] + lenb - cnt_b[i]), min(lena - asum + bsum, lenb - bsum + asum ));
        }
        res = min(res, lena - cnt_a[25] + lenb - cnt_b[25]);
        return res;
    }
};

[MongoCZK]

思路

前缀和+字符计数

代码

JavaScript

/**
 * @param {string} a
 * @param {string} b
 * @return {number}
 */
var minCharacters = function(a, b) {
    let da = new Array(26).fill(0);
    let db = new Array(26).fill(0);
    for(let i in a) {
        da[a.charCodeAt(i) - 97] ++;
    }
    for(let i in b) {
        db[b.charCodeAt(i) - 97] ++;
    }
    let an = a.length, bn = b.length, asum = 0, bsum = 0, res = Number.MAX_SAFE_INTEGER;
    for(let i = 0 ; i < 25 ; i ++) {
        // 前缀和计算
        asum += da[i];
        bsum += db[i];
        // 找最小值
        res = Math.min(res, an+bn-da[i]-db[i], an-asum+bsum, bn-bsum+asum);
    }
    // z的特殊处理
    return Math.min(res, an+bn-da[25]-db[25]);
};

[Tesla-1i]

class Solution: def minCharacters(self, A: str, B: str) -> int: counter_A = [0] 26 counter_B = [0] 26 for a in A: counter_A[ord(a) - ord('a')] += 1 for b in B: counter_B[ord(b) - ord('a')] += 1 ans = len(A) + len(B) for i in range(26): ans = min(ans, len(A) + len(B) - counter_A[i] - counter_B[i]) for i in range(1, 26): t = 0 for j in range(i, 26): t += counter_A[j] for j in range(i): t += counter_B[j] ans = min(ans, t) for i in range(1, 26): t = 0 for j in range(i, 26): t += counter_B[j] for j in range(i): t += counter_A[j] ans = min(ans, t) return ans

[guangsizhongbin]

class Solution { public int minCharacters(String a, String b) { int n = a.length(); int m = b.length(); int l[] = new int[26]; int r[] = new int[26];

   // 记录左边各字母出现次数
   for(int i = 0; i < a.length(); i++){
       l[a.charAt(i) - 'a']++;
   }

 // 记录右边各字母出现次数
   for(int i = 0; i < b.length(); i++){
       r[b.charAt(i) - 'a']++;
   }

   int lSum = 0;
   int rSum = 0;
   // 总长度
   int ans = n + m;

   // a - z
   for(int i = 0; i < 25; ++i){
       // 小于l[i]的字符串的个数
       lSum += l[i];
       // 小于r[i]的字符串的个数
       rSum += r[i];
       // 1. a中的每个字符严格小于b
       //       a 要交换的个数 n - lSum
       //       b 要交换的个数 rSum

       // 2. b中的每个字符严格小于a
       //       b 要交换的个数 m - rSum
       //       a 要交换的个数  lSum

       // 3. a中的每个字符要严格与b相同， 交换次数为 m + n - lSum - rSum
       ans = Math.min(ans, Math.min(Math.min(n + m - l[i] - r[i], n - lSum + rSum), m - rSum + lSum));
   }
   ans = Math.min(ans, n + m - l[25] - r[25]);
   return ans;
}

}