题目描述
给定两个长度相等的，由小写字母组成的字符串S1和S2，定义S1和S2的距离为两个字符串有多少个位置上的字母不相等。
现在牛牛可以选定两个字母X1和X2，将S1中的所有字母X1均替换成X2。（X1和X2可以相同）
牛牛希望知道执行一次替换之后，两个字符串的距离最少为多少。
示例1
输入："aaa","bbb"
输出：0
说明：牛牛可以将S1中的字符'a'全部替换成字符'b'，这样S1就变成了"bbb"，那么S1和S2的距离就是0
示例2
输入："aabb","cdef"
输出：3
说明：一种可行的方案是将S1中的字符'a'全部替换成字符'c'，那么S1变成了"ccbb"，和S2的距离是3
思路
使用字典count[26][26]记录S1、S2中的字符对。count[X1][X2]表示S1和S2中相同位置的字符对个数，即有多少个i使得S1[i]==X1,S2[i]==X2成立，这个值扫描一遍字符串即可得到；扫描的同时记录替换前的原始距离origin。然后枚举所有可能的X1、X2，此时的距离为origin+count[X1][X1]-count[X1][X2]，用一个变量min来保存结果，每次枚举时进行更新。
origin+count[X1][X1]-count[X1][X2]这个式子可能比较难理解，没关系，我们举个例子：
现在给出两个字符串aabbcb和aacbec，第一次遍历字符串的时候，可以依次得到6个字符对，根据字符对个数，对count数组初始化；同时根据题干中的定义：距离为两个字符串有多少个位置上的字母不相等，我们可以得到origin=3，也就是图中连线的3个字符对：b-c、c-e、b-c
枚举的时候，我们以X1=b、X2=c为例，也就是将S1中的所有字母b均替换成c（图中红色标记的c为替换的字符），对比上下两个S1、S2，我们可以发现这次替换的影响范围是S1中原来为b的位置并且S2中该位置的字符是c或b，也就是说对a-a和c-e这两个字符对是不产生影响的（如果存在类似于b-a、b-d这样的字符对也是不影响的，因为替换后c-a、c-d依然包含在origin中）。
那么来看影响范围内的字符对：b-c和b-b，替换后变成了c-c和c-b，这时产生了一个新的可以算入距离的字符对c-b（图中红线连接处），同时c-c不符合距离的定义，要从原始距离中刨去（图中打叉的地方）。有多少个需要算入和刨去的字符对呢？因为count数组记录的是替换前的状态，所以就要看这些字符对是由谁“变”来的：新算入的字符对原来是X1-X1，刨去的字符对原来是X1-X2，所以新的距离为origin+count[X1][X1]-count[X1][X2]
JAVA代码
public class Solution { /** * 计算最少的距离 * @param S1 string字符串 第一个字符串 * @param S2 string字符串 第二个字符串 * @return int整型 */ public int GetMinDistance (String S1, String S2) { int[][] count = new int[26][26]; int origin = 0; for(int i = 0; i < S1.length(); i++) { char ch1 = S1.charAt(i), ch2 = S2.charAt(i); count[ch1 - 'a'][ch2 - 'a'] ++; if(ch1 != ch2) origin++; } int min = S1.length(); for(int i = 0; i < 26; i++) { for(int j = 0; j < 26; j++) { min = Math.min(min, origin + count[i][i] - count[i][j]); } } return min; } }