通过仅设置一个 K 大小的子串位来最小化二进制字符串中的汉明距离
两个等长字符串之间的汉明距离是指另一个字符串中对应位置存在不同值的所有位置的数量。我们可以通过以下示例来理解:
S= "ramanisgoing"
T= "dishaisgoing"
这里，5 是两个字符串 S 和 T 之间的汉明距离，因为 raman 和 disha 是两个单词，它们使字符串相等。
问题描述
然而，在这个问题中，我们需要找到两个仅包含二进制数的字符串之间的汉明距离。用户会向我们提供一个字符串，比如说 S，以及另一个字符串，比如说 T，最初，我们假设其中只有"0"位，并且其大小与给定字符串的大小相同。我们将给出一个数字"k"，其值表示子字符串中元素个数，且子字符串中元素均为"1"。因此，我们将把这个大小为 k 的子字符串放在字符串 (T) 的任意位置，以最小化两个子字符串 S 和 T 之间的汉明距离。
让我们通过一些示例来理解这个问题。
输入 − S = "100111" K = 5
输出 − 3
解释 − 由于初始字符串 T 等于"000000"，因此字符串 T 将被更改为与字符串 S 进行比较，以找到 k=5 时的最小汉明距离，如下所示:"111110"和"011111"。
100111 和 000000 的汉明距离均为 4。 100111 和 111110 的汉明距离为 3，而 100111 和 011111 的汉明距离也为 3。
但由于 3 小于 4，因此最小汉明距离为 3。因此，答案为 3。
− S = "100101" K = 5
− 3
− 由于初始字符串 T 等于"000000"，因此字符串 T 将被更改为与字符串 S 进行比较，以找到 k=5 时的最小汉明距离，如下所示:"111110"和"011111"。
100101 和 000000 的汉明距离为 3。 100101 和 111110 的汉明距离为 4，而 100101 和 011111 的汉明距离也为 4。
但由于 3 小于 4，因此最小汉明距离为 3。因此，答案为 3。
问题解释
让我们尝试理解这个问题并找到解决方案。
解决方案 1 暴力解法
我们将通过改变子字符串在不同的起始点和结束点的位置来改变字符串 T，以便获得所有可能字符串中的最小汉明距离。
示例
以下是上述方法的 C++ 程序实现:
#include <bits/stdc++.h>
using namespace std;
// 编写一个函数，通过迭代获取最小汉明距离
int helper(string S,int k){
// n 是字符串的大小
int n=S.size();
// 取另一个字符串 T 并用与 S 大小相同的零位初始化它
string T;
for(int i=0;i<n;i++){
T+="0";
}
// 取另一个字符串 v 来初始化它，与 T 相同
string v=T;
// 将 mini 定义为 T 和 S 之间的汉明距离
int mini=0;
int l=0;
while(l<n){
if(S[l]!=T[l])mini++;
l++;
}
for(int i=0;i<n-k+1;i++){
int j=0,a=0,l=0;
// 通过改变大小为 k 的位来改变字符串 v
while(j<k){
v[j+i]='1';
j++;
}
// 计算汉明距离
while(l<n){
if(S[l]!=v[l])a++;
l++;
}
// 检查前一个汉明距离是否大于当前汉明距离，如果是，则替换该距离元素
if(mini>a){
mini=a;
}
// 再次将 v 指定为 T 字符串
v=T;
}
// 返回通过上述迭代找到的最小汉明距离
return mini;
}
int main() {
// 输入字符串 S
string S = "100101";
// 给出 k 的值，即子字符串的大小
int K = 5;
// 调用辅助函数
cout << "最小汉明距离为: "<< helper(S,K);
return 0;
}
输出
最小汉明距离为: 3
方案 2 优化方案
算法
使用前缀和数组计算 1 的个数，并将其存储为最小汉明距离
遍历字符串 S，找出字符串 S 中 K 个不同子字符串之间 1 的值。
如果 (i-1 < 0)，则 v 的值取为 arr[i+K-1]，否则，v 的值取为 (arr[i+K-1]-arr[i-1])
通过查找前一个汉明距离和当前汉明距离之间的最小值来存储最小值。
当前汉明距离可以通过将 K 个子字符串中零元素的数量 (K - v) 与当前 S 子串中零的个数为 (cnt - v)
最后，返回整体最小距离。
示例
Below is a C++ program impelementation of the above approach
#include <bits/stdc++.h>
using namespace std;
// 创建一个辅助函数，通过迭代获取最小汉明距离
int helper(string S, int K){
// n 是字符串的大小
int n = S.size();
// 初始化一个大小为 'n' 的数组
int arr[n];
if(S[0]=='0')arr[0]=0;
else arr[0]=1;
// 计算字符串 S 中 1 的个数
for (int i = 1; i < n; i++){
if(S[i]=='0')arr[i]=arr[i-1];
else arr[i]=arr[i-1]+1;
}
int cnt = arr[n - 1];
// 将 mini 定义为 T 和 S 之间的汉明距离
int mini = cnt;
// 遍历 S 以找到最小值
for (int i = 0; i < n - K; i++) {
int v;
if(i-1==-1)v=arr[i+K-1];
else v= arr[i+K-1]-arr[i-1];
// 存储最小值
mini = min(mini, cnt - v + (K - v));
}
// 返回最小汉明距离
return mini;
}
int main(){
// 输入字符串 S
string S = "100101";
// 给出 k 的值，即子字符串的大小
int K = 5;
// 调用辅助函数
cout << "最小汉明距离为: "<< helper(S,K);
return 0;
}
输出
最小汉明距离为: 3
结论
在本文中，为了找到最小汉明距离，我们首先会介绍一种简单的方法，但为了提高其时间复杂度，我们会使用前缀和数组的概念，通过它我们可以避免在同一个循环中在不同循环中重复计数。
