【Day 35 】2024-05-12 - 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 只由小写字母组成

[xil324]

class Solution(object):
    def minCharacters(self, a, b):
        """
        :type a: str
        :type b: str
        :rtype: int
        """
        self.min_changes = len(a) + len(b)
        count_a = [0] * 26
        count_b = [0] * 26
        for char in a:
            count_a[ord(char) - ord('a')] += 1
        for char in b:
            count_b[ord(char) - ord('a')] += 1
        presum_a, presum_b = [0 for i in range(27)], [0 for i in range(27)]
        for count_a_char, count_b_char in zip(count_a, count_b):
            self.min_changes = min(self.min_changes, len(a) + len(b) - count_a_char - count_b_char)
        self.calculate_min_changes(count_a, count_b)
        self.calculate_min_changes(count_b, count_a)
        return self.min_changes

    def calculate_min_changes(self, count_a, count_b): 
        print(count_a, count_b)
        for i in range(1, 26):
            changes = sum(count_a[i:]) + sum(count_b[:i])
            self.min_changes = min(changes, self.min_changes)

[zhiyuanpeng]

class Solution:
    def minCharacters(self, a: str, b: str) -> int:
        a = [ord(c)-ord("a") for c in a]
        b = [ord(c)-ord("a") for c in b]
        a_c = collections.Counter(a)
        a_l = len(a)
        b_c = collections.Counter(b)
        b_l = len(b)
        # case 3
        ans_3 = float("inf")
        for i in range(26):
            ans_3 = min(ans_3, a_l+b_l-a_c[i]-b_c[i])    
        # case 1 a < b
        ans_1 = self.a_smaller_b(a_c, b_c)
        # case 2 b < a
        ans_2 = self.a_smaller_b(b_c, a_c)
        ans = min(ans_1, ans_2, ans_3)
        return ans

    def a_smaller_b(self, x, y):
        # to make a smaller than b, iterate all the possible max char in a:
        # 1. all the char in a bigger than max shoud be changed to smaller than max
        # 2. all the char in b smaller than max in a should be changed to be bigger than max in a
        ans = float("inf")
        for i in range(1,26):
            t = 0
            for j in range(i, 26):
                t += x[j]
            for j in range(i):
                t += y[j]
            ans = min(ans, t)
        return and

[franklinsworld666]

代码

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

        s1,s2=len(a),len(b)

        pre1 = [str1[0]]+[0]*25
        pre2 = [str2[0]]+[0]*25
        suf1 = [0]*25 +[str1[-1]]
        suf2 = [0]*25 +[str2[-1]]

        for i in range(1,26):
            pre1[i] = pre1[i - 1] + str1[i] 
            pre2[i] = pre2[i - 1] + str2[i] 

        for i in range(24,-1,-1):
            suf1[i] = suf1[i+1]+str1[i] 
            suf2[i] = suf2[i+1]+str2[i]

        ans = s1 + s2

        for i in range(1,26):
            ans = min(ans, suf1[i]+ pre2[i-1])
            ans = min(ans, suf2[i] + pre1[i-1])

        for i in range(26):
            ans = min(ans,s1 +s2 - str1[i] - str2[i])

        return ans

[Martina001]

//时间复杂度：统计词频的复杂度为 O(n+m)，统计答案的复杂度为 O(C^2)，其中 C=26 为字符集大小 //空间复杂度：O(C)

 public int minCharacters(String a, String b) {
        // 枚举三种情况 找出最少操作次数
        // 1. 假设有个字符为x，则a中字符都得小于x，b中字符都要大于等于x
        // 2. a>=x,b<x
        // 3。 a==x，b也等于x
        // 为了快速枚举出所有的情况，可先把a和b中的字符出现次数存储下来
        int m  = a.length();
        int n = b.length();
        int []aArr = new int[26];
        int bArr[] = new int[26];

        for (int i = 0; i < m; i++) {
            aArr[a.charAt(i) - 'a'] ++;
        }
        for (int i = 0; i < n; i++) {
            bArr[b.charAt(i) - 'a'] ++;
        }

        int res = Integer.MAX_VALUE;
        // 枚举所有的x，统计操作数
        for(int x = 0;x<26;x++){

            // 特殊的，不存在任何字符严格小于'a' 所以要跳过
            if(x !=0){
                // 情况1的操作数为：
                int count1=0;
                for(int i=x;i<26;i++){
                    // 把a中比x大或者等的字符都操作一下
                    count1+=aArr[i];
                }
                for(int i=0;i<x;i++){
                    count1+=bArr[i];
                }

                // 情况2的操作数
                int count2=0;
                for(int i=0;i<x;i++){
                    // 把a中比x小的字符都操作一下
                    count2+=aArr[i];
                }
                for(int i=x;i<26;i++){
                    // 把b中比x大的字符都操作一下
                    count2+=bArr[i];
                }

                res = Math.min(Math.min(count1,count2),res);
            }

            // 情况3，将a和b中的字符全都变成x
            int count3 = (m-aArr[x])+(n-bArr[x]);

            res = Math.min(res,count3);
        }
        return res;
    }

[CathyShang]

class Solution:
    def minCharacters(self, a: str, b: str) -> int:
        coutA = [0]*26
        coutB = [0]*26 # count 26 nums
        for cur1 in a:
            coutA[ord(cur1)-ord('a')] +=1
        for cur2 in b:
            coutB[ord(cur2)-ord('a')] +=1
        ans = len(a)+len(b)

        # 条件3
        for i in range(26):
            ans = min(ans, len(a)+len(b)-coutA[i]-coutB[i])
        print(ans,"\n")
        # 条件1
        for i in range(1,26):
            t = 0
            for j in range(i,26):
                t += coutA[j]
            for k in range(i):
                t += coutB[k]
            ans = min(ans, t)
        print(ans,"\n")
        # 条件2
        for i in range(1,26):
            t = 0
            for j in range(i,26):
                t += coutB[j]
            for k in range(i):
                t += coutA[k]
            ans = min(ans, t)
        return ans

• Time O(m+n)
• Space O(26)

[Hermione666]

class Solution: def minCharacters(self, a: str, b: str) -> int: acnt = [0] 26 bcnt = [0] 26 an, bn = len(a), len(b)

    for c in a:
        acnt[ord(c) - ord('a')] += 1
    for c in b:
        bcnt[ord(c) - ord('a')] += 1

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

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

    # Handle the last character
    ans = min(ans, an - acnt[25] + bn - bcnt[25])

    return ans