The classic dynamic programming challenge known as the Longest Common Subsequence (LCS) conundrum involves determining the longest subsequence shared by two provided sequences.
Algorithm:
- Begin by setting up a two-dimensional array (matrix):
Generate a 2D array named dp with a size of (m + 1) rows by (n + 1) columns, where m and n represent the lengths of the two given strings.
- Populate the grid:
Traverse through the characters of both strings utilizing two nested loops. Define the loop iterators as i and j, iterating from 0 to m and 0 to n respectively.
- Validate character equality and non-repetition:
At every coordinate (i, j) within the matrix, validate whether the characters s1[i-1] and s2[j-1] match and do not recur within their individual substrings.
If they are identical and not recurring, assign dpi as dpi-1 plus 1.
If the values of i and j are not the same, assign dpi as the higher value between dpi-1 and dpi.
- The end outcome is:
The cell dpm located at the bottom-right corner will store the length of the Longest Common Subsequence (LCS) without any duplicate characters.
Program:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int longestCommonSubsequenceNoRepeatingChar(string s1, string s2) {
int m = s1.length();
int n = s2.length();
// Create a 2D array to store the length of the LCS for each pair of substrings
vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
// Fill the dp table using bottom-up dynamic programming
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
// If the characters are equal and non-repeating, then add 1 to the LCS length
if (s1[i - 1] == s2[j - 1] && count(s1.begin(), s1.begin() + i - 1, s1[i - 1]) == 0 &&
count(s2.begin(), s2.begin() + j - 1, s2[j - 1]) == 0) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
// If characters are not equal, take the maximum of the previous LCS lengths
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
// The result is stored in the bottom-right cell of the dp table
return dp[m][n];
}
int main() {
string s1 = "ABCBDAB";
string s2 = "BDCAB";
int result = longestCommonSubsequenceNoRepeatingChar(s1, s2);
cout << "Length of the longest common subsequence with no repeating characters: " << result << endl;
return 0;
}
Output:
Length of the longest common subsequence with no repeating characters: 2
Complexity analysis:
Time Complexity:
The algorithm's time complexity is O(m * n), where 'm' and 'n' represent the sizes of input strings s1 and s2. This is due to a nested loop that traverses each character in both strings, with constant-time operations performed within the loop.
Space Complexity:
The space complexity also amounts to O(m * n). This arises from the 2D array dp with dimensions (m + 1) x (n + 1) employed for holding the lengths of the Longest Common Subsequence (LCS) for every substring pair. The space complexity scales linearly with the dimensions of this matrix.
In the most unfavorable scenario, it is necessary to populate the complete matrix, resulting in a space complexity of O(m * n).
Approach 1: Using a Recursive Approach with Memorization
Utilizing a recursive strategy with memoization entails decomposing the issue into smaller subtasks and storing the outcomes of these subtasks to prevent duplicate computations.
Program:
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
// Function to calculate LCS length with no repeating characters using recursion and memorization
int lcsRecursiveWithMemo(string &s1, string &s2, int i, int j, unordered_map<string, int> &memo) {
// Base case: when either of the indices reaches 0, the LCS length is 0
if (i == 0 || j == 0) {
return 0;
}
// Create a unique key for the memoization table
string key = to_string(i) + "_" + to_string(j);
// Check if the result for the current subproblem is already memoized
if (memo.find(key) != memo.end()) {
return memo[key];
}
// Check if the characters are equal
bool charactersEqual = (s1[i - 1] == s2[j - 1]);
// Check for non-repeating characters in both substrings
for (int k = i - 1; k >= 0; --k) {
if (s1[k] == s1[i - 1]) {
charactersEqual = false;
break;
}
}
for (int k = j - 1; k >= 0; --k) {
if (s2[k] == s2[j - 1]) {
charactersEqual = false;
break;
}
}
// If characters are equal and non-repeating, recursively calculate LCS
if (charactersEqual) {
memo[key] = 1 + lcsRecursiveWithMemo(s1, s2, i - 1, j - 1, memo);
} else {
// If characters are not equal, take the maximum of the previous LCS lengths
memo[key] = max(lcsRecursiveWithMemo(s1, s2, i - 1, j, memo), lcsRecursiveWithMemo(s1, s2, i, j - 1, memo));
}
return memo[key];
}
// Main function to initiate LCS calculation with memoization
int longestCommonSubsequenceNoRepeatingCharRecursive(string &s1, string &s2) {
int m = s1.length();
int n = s2.length();
unordered_map<string, int> memo;
return lcsRecursiveWithMemo(s1, s2, m, n, memo);
}
int main() {
string s1 = "ABCBDAB";
string s2 = "BDCAB";
int result = longestCommonSubsequenceNoRepeatingCharRecursive(s1, s2);
cout << "Length of the longest common subsequence with no repeating characters: " << result << endl;
return 0;
}
Output:
Length of the longest common subsequence with no repeating characters: 0
Explanation:
- Recursive Function:
The primary function is lcsRecursiveWithMemo, responsible for computing the length of the Longest Common Subsequence (LCS) without duplicate characters through a recursive methodology.
Base Scenario:
The function includes a base case to halt the recursion process.
When either i or j index reaches zero, it signifies the conclusion of one of the input strings. In these scenarios, the length of the LCS is deemed as zero.
- Caching:
Committing information to memory is employed to enhance the efficiency of the recursive approach. This process entails saving and utilizing previously derived outcomes to prevent unnecessary computations.
A lookup table (unordered_map) is employed to save outcomes according to the current indices i and j.
- Check for Non-Repeating Characters:
The initial code utilized the count function to validate unique characters. Nonetheless, a different method involving explicit loops was adopted because of a compilation issue.
The function verifies whether the current character under evaluation in the Longest Common Subsequence (LCS) is unique within its substring. Should it be a repeated character, the LCS cannot contain duplicates.
- Algorithm:
If the characters at their current positions are identical and not duplicated, the function will iteratively determine the length of the LCS for the preceding positions (i-1, j-1) and increment it by 1.
If the characters are unequal, the algorithm selects the larger of the two LCS lengths calculated by excluding either the final character of string s1 or the final character of string s2.
- Outcome:
The end outcome is achieved by invoking the recursive function using the lengths of the input strings as starting indices. This outcome signifies the size of the longest common subsequence without duplicated characters.
- Main Function:
The longestCommonSubsequenceNoRepeatingCharRecursive function acts as a starting point, where it initializes the memoization table and triggers the recursive function.
- For instance:
The demonstration in the main function showcases the application using the strings "ABCBDAB" and "BDCAB". Subsequently, the output is displayed on the console.
Complexity analysis:
Time Complexity:
The algorithm's time complexity is O(m * n), with 'm' and 'n' representing the respective lengths of input strings s1 and s2.
By leveraging memorization, the function prevents repetitive calculations by saving and reusing outcomes for previously solved subtasks. This approach notably cuts down on the recursive function calls, leading to a more optimized time complexity compared to the basic recursive method.
Space Complexity:
Due to the memoization table, the spatial complexity is O(m n). This table retains outcomes for every distinct pair of indices (i, j) throughout the recursive invocations. If the worst-case scenario occurs, where the entire table must be populated, it results in O(m n) spatial complexity.
In addition to the memory table, the space complexity also considers the stack of recursive calls, which may reach the deepest level of the recursion tree. In the most unfavorable scenario, it could amount to O(m + n).
