Medium

题目描述

给你两个长度相等的字符串 s 和 t。在一步操作中，你可以选择字符串 t 中的任何一个字符，并将其替换为另一个字符。

返回使 t 成为 s 的字母异位词的最小步骤数。

字母异位词指字母相同，但排列不同（或相同）的字符串。

示例 1：

输入：s = "bab", t = "aba"
输出：1
解释：用 'b' 替换 t 中的第一个 'a'，t = "bba"，这是 s 的一个字母异位词。

示例 2：

输入：s = "leetcode", t = "practice"
输出：5
解释：用合适的字符替换 t 中的 'p'、'r'、'a'、'i'、'c'，使 t 成为 s 的字母异位词。

示例 3：

输入：s = "anagram", t = "mangaar"
输出：0
解释："anagram" 和 "mangaar" 互为字母异位词。

提示：

  • 1 <= s.length <= 5 * 10^4
  • s.length == t.length
  • s 和 t 只包含小写英文字母

解题思路

解题思路

这道题要求我们计算将字符串 t 转换为字符串 s 的字母异位词所需的最小步骤数。

核心思想： 字母异位词意味着两个字符串包含相同的字符及其频次。因此，我们需要统计两个字符串中各字符的频次差异。

算法步骤：

  1. 统计字符串 s 和 t 中每个字符的出现频次
  2. 对于每个字符，如果在 t 中的频次少于在 s 中的频次，说明需要将 t 中的其他字符替换为这个字符
  3. 所有需要增加的字符数量之和就是最小步骤数

优化思路： 我们可以用一个频次数组来同时记录差异。遍历 s 时对应字符计数 +1，遍历 t 时对应字符计数 -1。最后统计所有正数的和，这些正数表示 t 中缺少的字符数量。

时间复杂度为 O(n)，空间复杂度为 O(1)（因为只有26个小写字母）。

代码实现

class Solution {
public:
    int minSteps(string s, string t) {
        vector<int> count(26, 0);
        
        // 统计字符频次差异
        for (int i = 0; i < s.length(); i++) {
            count[s[i] - 'a']++;
            count[t[i] - 'a']--;
        }
        
        // 计算需要替换的字符数
        int steps = 0;
        for (int i = 0; i < 26; i++) {
            if (count[i] > 0) {
                steps += count[i];
            }
        }
        
        return steps;
    }
};

class Solution:
    def minSteps(self, s: str, t: str) -> int:
        count = [0] * 26
        
        # 统计字符频次差异
        for i in range(len(s)):
            count[ord(s[i]) - ord('a')] += 1
            count[ord(t[i]) - ord('a')] -= 1
        
        # 计算需要替换的字符数
        steps = 0
        for c in count:
            if c > 0:
                steps += c
        
        return steps

public class Solution {
    public int MinSteps(string s, string t) {
        int[] count = new int[26];
        
        // 统计字符频次差异
        for (int i = 0; i < s.Length; i++) {
            count[s[i] - 'a']++;
            count[t[i] - 'a']--;
        }
        
        // 计算需要替换的字符数
        int steps = 0;
        for (int i = 0; i < 26; i++) {
            if (count[i] > 0) {
                steps += count[i];
            }
        }
        
        return steps;
    }
}

var minSteps = function(s, t) {
    const count = new Array(26).fill(0);
    
    // 统计字符频次差异
    for (let i = 0; i < s.length; i++) {
        count[s.charCodeAt(i) - 97]++;
        count[t.charCodeAt(i) - 97]--;
    }
    
    // 计算需要替换的字符数
    let steps = 0;
    for (let i = 0; i < 26; i++) {
        if (count[i] > 0) {
            steps += count[i];
        }
    }
    
    return steps;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历两个字符串各一次，其中 n 为字符串长度
空间复杂度O(1)使用固定大小的数组存储26个字母的频次

相关题目