检查是否可以通过将 A[i] 更改为 A[i+1] 或将 A[i]..A[i+K-1] 更改为 A[i]+1 来将字符串 A 转换为字符串 B

data structurec++programming

我们给出了两个字符串，我们必须检查是否可以通过执行任意次数的特定任务将第一个字符串转换为另一个字符串。只能对给定的第一个字符串执行的任务如下:

选择任何索引 i，使得 i < length(A) -1，并将第 i 个字符与下一个字符交换。
我们给出了一个整数 k，我们可以选择第一个字符串的任意连续 k 个索引，前提是它们相同，并且可以将它们更新为下一个字符(仅当可能时，对于字符 z 不可能)。例如:可以将 a 更新为 b、将 c 更新为 d、将 y 更新为 z 等。

我们必须判断是否可以通过多次应用上述任务使两个给定的字符串相等。

示例

输入

string str1 = "abcbcacba"
string str2 = "xxxyyyzzz"
int k = 3

输出

是的，可以将第一个字符串转换为第二个字符串

解释:第一个字符串中有三个字符 a、b 和 c。此外，这三个字符的频率相同。我们可以将字符"a"的频率全部增加到"z"，因为第二个字符串中有三个 z，类似地，b 到 x，c 到 y。

输入

string str1 = "abcbcacba"
string str2 = "xxxzzzyyy"
int k = 2;

输出

不，无法将第一个字符串转换为第二个字符串

解释:我们只能将两个字符分组，因为 k 的值为 2，并且我们的不同字符成对出现，因此无法更改它们。

观察

我们必须使两个字符串相等，并且我们只能应用上述操作。我们可以在这里做出的观察是:

我们可以任意次交换字符，因此字符的顺序无关紧要，唯一重要的是字符的频率。

我们可以增加字符的频率而不是减少它，因此如果有些字符的 ASCII 值大于第二个字符串的最大字符，那么就不可能使两个字符串相同。

此外，如果两个字符串的大小不相同，那么显然不可能使两个字符串相同。

方法

我们已经看到了示例和问题观察，让我们进入实施步骤:

首先，我们将检查字符串长度，如果字符串的长度不相同，则不可能使它们相等，因此返回 false。
我们将创建两个数组来存储两个字符串的字符频率。
然后我们将使用 for 循环遍历字符串以获取频率。
之后，我们将使用额外的变量遍历频率数组来计算剩余的额外字符。
我们将使用 if-else 条件来检查是否可以根据当前索引频率使字符串与当前索引相同。

示例

#include <bits/stdc++.h>
using namespace std; 

bool isPos(string str1, string str2, int k){
    int len = str1.size(); // 获取字符串 1 的长度
    // 如果两个字符串的长度不相同，则返回 false
    if(len != str2.size()){
    return false;
    }
    // 获取字符的频率
    int freq1[26] = {0};
    int freq2[26] = {0};
    // 获取频率
    for(int i=0; i<len; i++){
        freq1[str1[i]-'a']++;
    }
    for(int i=0; i<len; i++){
        freq2[str2[i]-'a']++;
    }
    int cnt = 0; // 维护剩余字符的数量
    // 遍历频率数组
    for(int i=0; i<26; i++){
        freq1[i] += cnt; // 添加前面更多的字符
        if(freq2[i] > freq1[i]){
            // 我们无法创建字符串
            return false;
        }
        else if((freq1[i] - freq2[i]) % k){
            // 一些字符剩余不是 k 的倍数，我们无法使它们与另一个字符相同
            return false;
        } else{
            cnt += freq1[i]-freq2[i];
        }
    }
    return true;
}
int main(){
    // 给定字符串
    string str1 = "abccbabca";
    string str2 = "xxxzzzyyy";
    int k = 3; // 给定数字
    // 调用函数
    bool res = isPos(str1, str2, k);
    if(res == true){
        cout<<"是的，可以将第一个字符串转换为第二个字符串"<<endl;
    } else{
        cout<<"不，不能将第一个字符串转换为第二个字符串"<<endl;
    }
}

输出

是的，可以将第一个字符串转换为第二个字符串

时间和空间复杂度

上述代码的时间复杂度为 O(N)，其中 N 是给定字符串的大小。

上述代码的空间复杂度为 O(1) 或常数，因为我们使用了一些额外的空间，但该空间对于所有输入大小都是常数。

结论

在本教程中，我们实现了一个程序来检查如果我们对第一个字符串执行无限数量的给定操作，两个给定的字符串是否可以相等。操作是:选择任何索引 i，使得 i < length(A) -1 并将第 i 个字符与下一个字符交换，我们给出一个整数 k，并且我们可以选择第一个字符串的任何连续 k 个索引，前提是它们相同并且可以将它们更新为下一个字符。我们已经在线性时间和恒定空间复杂度内实现了该程序。