1737. 修改最少字符使满足三个条件之一

Medium

题目描述

给你两个由小写字母组成的字符串 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
解释：最好的方法是将 b 改为 "eee" 来满足条件 1。

约束条件：

1 <= a.length, b.length <= 10^5
a 和 b 只包含小写字母。

解题思路

这道题要求我们找到最少的操作次数来满足三个条件之一。我们需要分别计算满足每个条件的最少操作数，然后取最小值。

解题思路：

条件1和2（字典序严格小于）：我们可以枚举分界点。对于条件1，假设 a 中所有字符都小于等于字符 c，b 中所有字符都大于字符 c。我们需要统计每个字符串中字符的频次，然后计算需要修改的字符数。
条件3（相同字符）：枚举26个小写字母，对于每个字母，计算将两个字符串都改成该字母所需的操作数。

具体实现：

使用数组统计两个字符串中各字母的出现次数
对于条件1和2，枚举分界字符（‘a’到’y’），计算所需操作数
对于条件3，枚举目标字符（‘a’到’z’），计算所需操作数
返回三种条件下的最小操作数

需要注意的是，条件1和2中分界字符不能是’z’（因为没有比’z’更大的字母）和’a’（因为没有比’a’更小的字母）。

代码实现

class Solution {
public:
    int minCharacters(string a, string b) {
        vector<int> countA(26, 0), countB(26, 0);
        
        // 统计字符频次
        for (char c : a) countA[c - 'a']++;
        for (char c : b) countB[c - 'a']++;
        
        int result = INT_MAX;
        
        // 条件1: a中所有字符 < b中所有字符
        for (int i = 0; i < 25; i++) {  // 'a' 到 'y'
            int ops = 0;
            // a中大于i的字符需要修改
            for (int j = i + 1; j < 26; j++) {
                ops += countA[j];
            }
            // b中小于等于i的字符需要修改
            for (int j = 0; j <= i; j++) {
                ops += countB[j];
            }
            result = min(result, ops);
        }
        
        // 条件2: b中所有字符 < a中所有字符
        for (int i = 0; i < 25; i++) {  // 'a' 到 'y'
            int ops = 0;
            // b中大于i的字符需要修改
            for (int j = i + 1; j < 26; j++) {
                ops += countB[j];
            }
            // a中小于等于i的字符需要修改
            for (int j = 0; j <= i; j++) {
                ops += countA[j];
            }
            result = min(result, ops);
        }
        
        // 条件3: a和b都由同一个字母组成
        for (int i = 0; i < 26; i++) {
            int ops = a.length() + b.length() - countA[i] - countB[i];
            result = min(result, ops);
        }
        
        return result;
    }
};

class Solution:
    def minCharacters(self, a: str, b: str) -> int:
        count_a = [0] * 26
        count_b = [0] * 26
        
        # 统计字符频次
        for c in a:
            count_a[ord(c) - ord('a')] += 1
        for c in b:
            count_b[ord(c) - ord('a')] += 1
        
        result = float('inf')
        
        # 条件1: a中所有字符 < b中所有字符
        for i in range(25):  # 'a' 到 'y'
            ops = 0
            # a中大于i的字符需要修改
            for j in range(i + 1, 26):
                ops += count_a[j]
            # b中小于等于i的字符需要修改
            for j in range(i + 1):
                ops += count_b[j]
            result = min(result, ops)
        
        # 条件2: b中所有字符 < a中所有字符
        for i in range(25):  # 'a' 到 'y'
            ops = 0
            # b中大于i的字符需要修改
            for j in range(i + 1, 26):
                ops += count_b[j]
            # a中小于等于i的字符需要修改
            for j in range(i + 1):
                ops += count_a[j]
            result = min(result, ops)
        
        # 条件3: a和b都由同一个字母组成
        for i in range(26):
            ops = len(a) + len(b) - count_a[i] - count_b[i]
            result = min(result, ops)
        
        return result

public class Solution {
    public int MinCharacters(string a, string b) {
        int[] countA = new int[26];
        int[] countB = new int[26];
        
        // 统计字符频次
        foreach (char c in a) {
            countA[c - 'a']++;
        }
        foreach (char c in b) {
            countB[c - 'a']++;
        }
        
        int result = int.MaxValue;
        
        // 条件1: a中所有字符 < b中所有字符
        for (int i = 0; i < 25; i++) {  // 'a' 到 'y'
            int ops = 0;
            // a中大于i的字符需要修改
            for (int j = i + 1; j < 26; j++) {
                ops += countA[j];
            }
            // b中小于等于i的字符需要修改
            for (int j = 0; j <= i; j++) {
                ops += countB[j];
            }
            result = Math.Min(result, ops);
        }
        
        // 条件2: b中所有字符 < a中所有字符
        for (int i = 0; i < 25; i++) {  // 'a' 到 'y'
            int ops = 0;
            // b中大于i的字符需要修改
            for (int j = i + 1; j < 26; j++) {
                ops += countB[j];
            }
            // a中小于等于i的字符需要修改
            for (int j = 0; j <= i; j++) {
                ops += countA[j];
            }
            result = Math.Min(result, ops);
        }
        
        // 条件3: a和b都由同一个字母组成
        for (int i = 0; i < 26; i++) {
            int ops = a.Length + b.Length - countA[i] - countB[i];
            result = Math.Min(result, ops);
        }
        
        return result;
    }
}

var minCharacters = function(a, b) {
    const countA = new Array(26).fill(0);
    const countB = new Array(26).fill(0);
    
    // 统计字符频次
    for (const c of a) {
        countA[c.charCodeAt(0) - 'a'.charCodeAt(0)]++;
    }
    for (const c of b) {
        countB[c.charCodeAt(0) - 'a'.charCodeAt(0)]++;
    }
    
    let result = Number.MAX_SAFE_INTEGER;
    
    // 条件1: a中所有字符 < b中所有字符
    for (let i = 0; i < 25; i++) {  // 'a' 到 'y'
        let ops = 0;
        // a中大于i的字符需要修改
        for (let j = i + 1; j < 26; j++) {
            ops += countA[j];
        }
        // b中小于等于i的字符需要修改
        for (let j = 0; j <= i; j++) {
            ops += countB[j];
        }
        result = Math.min(result, ops);
    }
    
    // 条件2: b中所有字符 < a中所有字符
    for (let i = 0; i < 25; i++) {  // 'a' 到 'y'
        let ops = 0;
        // b中大于i的字符需要修改
        for (let j = i + 1; j < 26; j++) {
            ops += countB[j];
        }
        // a中小于等于i的字符需要修改
        for (let j = 0; j <= i; j++) {
            ops += countA[j];
        }
        result = Math.min(result, ops);
    }
    
    // 条件3: a和b都由同一个字母组成
    for (let i = 0; i < 26; i++) {
        const ops = a.length + b.length - countA[i] - countB[i];
        result = Math.min(result, ops);
    }
    
    return result;
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度	值
时间复杂度	O(n + m + 26²) = O(n + m)
空间复杂度	O(1)

其中 n 和 m 分别是字符串 a 和 b 的长度。虽然有嵌套循环，但内层循环最多执行26次，是常数级别。

题目描述#

解题思路#

代码实现#

复杂度分析#

题目描述

解题思路

代码实现

复杂度分析