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

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

选择任意索引i，使得i < length(A) -1，并将第i个字符与下一个字符交换。
我们给定了一个整数k，如果可以选择连续的k个索引，则只能选择第一个字符串的这些索引（如果它们相同），并将它们更新为它们的下一个字符（仅当可能时，字符z除外）。例如：可以更新a为b，c为d，y为z等。

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

示例示例

输入

string str1 = “abcbcacba”
string str2 = “xxxyyyzzz”
int k = 3

输出

Yes, it is possible to convert the first string to the second

解释：在第一个字符串中，我们有三个字符a，b和c。而且，这三个字符的频率都相同。我们可以将字符’a’的频率一起增加到’z’，因为在第二个字符串中我们有三个z；类似地，我们可以将字符’b’增加到x，字符’c’增加到y。

输入

string str1 = “abcbcacba”
string str2 = “xxxzzzyyy”
int k = 2;

输出

No, it is not possible to convert the first string to the second

解释: 当 k 的值为 2 且我们的不同字符是以3对出现时，我们只能将两个字符分组，并不可能改变它们。

观察:

我们必须使两个字符串相等，并且只能应用上面给出的操作。我们可以在这里得出以下观察结果：

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

我们可以增加字符的频率，但不能减少，因此如果一些字符的ASCII值大于第二个字符串的最大字符，则无法使两个字符串相同。

此外，如果两个字符串的尺寸不同，那么显然无法使两个字符串相同。

方法:

我们已经看过问题的例子和观察结果，现在让我们来实施的步骤:

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

例子:

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

bool isPos(string str1, string str2, int k){
   int len = str1.size(); // getting length of the string 1 
   // if the length of both the strings is not the same then return false
   if(len != str2.size()){
      return false;
   }
   // getting the frequency of the characters
   int freq1[26] = {0};
   int freq2[26] = {0}; 
   // getting the frequencies 
   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; // maintaining count of the remaining characters
   // traversing over the frequency array 
   for(int i=0; i<26; i++){
      freq1[i] += cnt; // adding the previous characters which are more 
      if(freq2[i] > freq1[i]){
         // we are not able to create the string 
         return false;
      }
      else if((freq1[i] - freq2[i]) % k){
         // some characters lefts which are not multiple of k and we are not able to make them same of another 
         return false;
      } else{
         cnt += freq1[i]-freq2[i];
      }
   }
   return true;
}
int main(){
   // given string 
   string str1 = "abccbabca";
   string str2 = "xxxzzzyyy";
   int k = 3; // given number 
   // calling to the function 
   bool res = isPos(str1, str2, k);
   if(res == true){
      cout<<"Yes, it is possible to convert the first string to the second"<<endl;
   } else{
      cout<<"No, it is not possible to convert the first string to the second"<<endl;
   }
}

输出

Yes, it is possible to convert the first string to the second

时间和空间复杂度

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

以上代码的空间复杂度是O(1)或常数，因为我们使用了一些额外的空间，但是对于所有输入大小来说，这个空间是恒定的。

结论

在本教程中，我们实现了一个程序，检查两个给定的字符串在对第一个字符串执行无限次给定操作后是否可以相等。这些操作是：选择任意索引i，其中i < length(A) -1，并将第i个字符与下一个字符交换，并且我们给定一个整数k，只有当第一个字符串的连续k个索引相同且可以更新它们为下一个字符时，我们才能选择它们。我们使用线性时间和常数空间复杂度实现了这个程序。