求字符串转指定变位词最少步数的算法执行时间优化方案

给定仅由小写英文字母组成、长度相等的两个字符串s和t，需要通过替换t中的字符，将t修改为s的变位词，每次替换计为1步，要求输出所需的最少步数。

示例 #

输入样例：
s = "friend"
t = "family"
预期输出：4

原因：按任意顺序将t中的'a'、'm'、'l'、'y'替换为'r'、'e'、'n'、'd'即可。

• HashMap属于过度设计：仅26个小写字母的取值范围，完全不需要哈希表的动态扩容、哈希计算、冲突处理、包装类拆装箱等额外开销
• 遍历逻辑冗余：原代码需要分别遍历两个哈希表计算差值，额外增加了无效循环次数

1. 替换HashMap为固定长度数组 #

直接用长度为26的int数组统计字符频率，索引对应c - 'a'，数组的随机访问效率远高于哈希表，无任何附加开销。

2. 合并计算逻辑 #

无需单独维护两个频率数组，先统计s的字符频率，再遍历t的字符直接抵消对应频率，最后统计s剩余的正频率之和就是最终答案，连除以2的计算步骤都可以省略。

3. 输入输出优化（针对竞赛大输入场景） #

Java的Scanner本身性能较差，大输入量场景下可替换为BufferedReader进一步提升运行速度。

package com.task;

import java.util.Scanner;

class Solution {
    public int minSteps(String s, String t) {
        int[] freq = new int[26];
        // 统计s的字符频率
        for (char c : s.toCharArray()) {
            freq[c - 'a']++;
        }
        // 用t的字符抵消频率
        for (char c : t.toCharArray()) {
            freq[c - 'a']--;
        }
        // 正频率之和就是需要替换的次数
        int res = 0;
        for (int count : freq) {
            if (count > 0) {
                res += count;
            }
        }
        return res;
    }
    
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        String s = scan.nextLine();
        String t = scan.nextLine();
        System.out.println(new Solution().minSteps(s, t));
    }
}

大输入场景下输入部分可替换为：

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    String s = br.readLine();
    String t = br.readLine();
    System.out.println(new Solution().minSteps(s, t));
}

时间复杂度保持O(n)的前提下，常数级开销大幅降低，运行速度通常可提升5~10倍，内存占用也会明显减少。

内容的提问来源于stack exchange，提问作者Sharad Nanda