无重复字符的最长公共子序列

---

在一个字符串中，子序列是可以通过删除其中一些字符形成的字符串，这意味着它包含字符串中的一些字符，可能是全部或部分，并且所有字符都将以与字符串相同的顺序出现。在两个字符串中，我们必须找到最长的公共子序列，该子序列不包含任何重复的字符。

示例

输入

string str1 = "aabcadjmuorrrcc"
string str2 = "adbcwcadjomrorlc" 

输出

The length of the longest common subsequence is: 8

解释：在上述给定的字符串中，我们有最大的公共子序列“abcadjmrrc”，如果我们只考虑唯一的字符，则通过删除出现两次的'a'、'c'和'r'，我们将得到“abcdjmor”。

输入

string str1 = “abcdedf”
string str2 =  “xayjklf”

输出

The length of the longest common subsequence is: 2

解释：这里，我们只有两个共同的字符，它们都是'af'。

递归方法

在这种方法中，我们将确定两个给定字符串中所有共同的子序列，并将维护唯一字符计数，以便任何字符都不能重复。

我们将创建一个递归函数，该函数将把两个字符串以及指示两个字符串当前索引的指针作为参数。此外，我们还将传递一个整数，该整数将使用位掩码的概念来存储当前公共子序列中已存在的字符。

我们将设置当前字符的ASCII值减去字符'a'的ASCII值的位，以将它们存储在数字中。

示例

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

// recursion function 
int rec(string& str1, string& str2, int i, int j, int bit){
   if(i == str1.size() || j == str2.size()){
      return 0;
   }
   if((str1[i] == str2[j])  && (bit & (1 << (str1[i]-'0'))) == 0){
      bit = bit | (i << (str1[i]-'0'));
      return 1 + rec(str1, str2, i+1, j+1, bit);
   } else{ 
      return max(rec(str1,str2,i+1,j,bit), rec(str1,str2,i,j+1,bit));
   }
}
// helper function
int findlen(string str1, string str2){
   int bit = 0; // integer to store the bit values 
   // calling to the recursion function to get the answer 
   int ans = rec(str1, str2, 0, 0, bit);
   return ans; // returning the answer 
}
// main function 
int main(){
   string str1 = "aabcadjmuorrrcc"; // given first string
   string str2 = "adbcwcadjomrorlc"; // given second string 
   // calling the funciton 
   cout<<"The length of the longest common subsequence is: "<<findlen(str1,str2)<<endl;
}

输出

The length of the longest common subsequence is: 8

时间和空间复杂度

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

上述代码的空间复杂度为 O(N)，这是由于递归栈造成的。

记忆化方法

在前面的一种方法中，函数的调用次数很高，更准确地说，存在指数级的调用，这使得该方法效率低下。因此，我们将使用记忆化方法来存储我们已经计算出的调用的结果。

我们将使用哈希映射来存储键，因为我们使用的是一个 26 位的整数（用于标记唯一字符），这使得使用数组创建 dp 表变得不可能。

我们将遵循前面的代码，只需添加几行新的记忆化技术，即可定义和初始化映射。然后将结果存储在映射中，并检查键是否已存在于映射中。

示例

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

// map for memoization 
map<string, int> memo;
// recursion function 
int rec(string& str1, string& str2, int i, int j, int bit){
   if(i == str1.size() || j == str2.size()){
      return 0;
   }
   string str = to_string(i) + to_string(j) + to_string(bit);
   if(memo.find(str) != memo.end()){
      return memo[str];
   }
   if((str1[i] == str2[j])  && (bit & (1 << (str1[i]-'0'))) == 0){
      bit = bit | (i << (str1[i]-'0'));
      memo[str] = 1 + rec(str1, str2, i+1, j+1, bit);
   } else{ 
      memo[str] = max(rec(str1,str2,i+1,j,bit), rec(str1,str2,i,j+1,bit));
   }
   return memo[str];
}
// helper function
int findlen(string str1, string str2){
   int bit = 0; // integer to store the bit values 
   memo = {}; // initializing the map
   // calling to the recursion function to get the answer 
   int ans = rec(str1, str2, 0, 0, bit);
   return ans; // returning the answer 
}
// main function 
int main(){
   string str1 = "aabcadjmuorrrcc"; // given first string
   string str2 = "adbcwcadjomrorlc"; // given second string 
   // calling the function 
   cout<<"The length of the longest common subsequence is: "<<findlen(str1,str2)<<endl;
}

输出

The length of the longest common subsequence is: 8

时间和空间复杂度

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

上述代码的空间复杂度为 O(N*M)，因为我们使用哈希映射来存储记忆化结果。

结论

在本教程中，我们实现了一个程序，用于查找两个给定字符串中不包含任何重复字符的最长子序列。首先，我们实现了递归方法，然后我们使用哈希映射来存储已计算出的调用的结果并返回答案。上述代码的时间复杂度为 O(N*M)，空间复杂度也相同。