在C ++中对第二个字符串执行交换后，找到两个字符串之间的最长公共前缀

假设我们有两个字符串str1和str2。在第二个字符串上执行零次或多次操作后，找到它们之间最长的公共前缀。在每个操作中，我们可以交换任意两个字母。因此，如果str1 =“ HERE”，str2 =“ THERE”，则输出将为4。只需交换字符即可将第二个字符串设置为“ HERET”。因此，最长前缀的长度为4。

众所周知，我们只能在str2上交换。并且矩阵的长度应最大化。因此，其想法是遍历str1，并检查str1中当前字符的频率是否等于或小于str2中的当前字符的频率。如果是，则向前移动字符串a，否则中断并打印字符串str1的一部分长度，直到字符串str2中的某个字符与之匹配。

示例

#include <iostream>
using namespace std;
void longestPrefix(string str1, string str2) {
   int frequency[26]={0};
   int a = str1.length();
   int b = str2.length();
   for (int i=0 ;i<b ; i++) {
      frequency[str2[i] - 97] += 1;
   }
   int c = 0;
   for (int i=0 ;i<a ; i++) {
      if (frequency[str1[i] - 97] > 0){
         c += 1;
         frequency[str1[i] - 97] -= 1;
      } else
      break;
   }
   cout<<"Length of longest common prefix: " << c;
}
int main() {
   string str1="here", str2 = "there";
   longestPrefix(str1, str2);
}

输出结果

Length of longest common prefix: 4