Given two strings s1 and s2, the task is to find the length of the longest common subsequence with no repeating character.
Examples:
Input: s1= “aabbcc”, s2= “aabc”
Output: 3
Explanation: “aabc” is longest common subsequence but it has two repeating character ‘a’.
So the required longest common subsequence with no repeating character is “abc”.Input: s1= “aabcad”, s2= “adbcwcad”
Output: 4
Explanation: The subsequences are “abcd” or “bcad”.
Approach: The approach to solve the problem is similar to that of the longest common subsequence using recursion but, also needs to keep track that no two characters are repeated in a subsequence. Follow the steps mentioned below:
- For each character at the ith position, that character can be part of a sequence or not.
- Generate every sequence in this way and check for the longest common sequence.
- To keep track of which characters are included in the subsequence use bits of variable “store”.
- Each bit of variable “store”, tells Whether that alphabet is already present or not in a subsequence.
- bit at 0th position corresponds to character ‘a’, at position 1 corresponds to ‘b’, similarly 2 to ‘c’ so on.
Below is the implementation of the above approach.
C++
// C++ program to implement the approach#include <bits/stdc++.h>using namespace std;// Function to find lcs// with no repeating characterint find(string s1, string s2, int N, int M, long long store){ if (N == 0 || M == 0) return 0; if (s1[N - 1] == s2[M - 1] && ((store >> (s1[N - 1] - 'a')) & 1) == 0) { store = (store | (1 << (s1[N - 1] - 'a'))); return 1 + find(s1, s2, N - 1, M - 1, store); } else return max(find(s1, s2, N - 1, M, store), find(s1, s2, N, M - 1, store));}// Driver codeint main(){ string s1, s2; s1 = "aabbcc"; s2 = "aabc"; long long store = 0; cout << find(s1, s2, s1.length(), s2.length(), store); return 0;} |
Java
// Java program for the above approachclass GFG { // Function to find lcs // with no repeating character static int find(String s1, String s2, int N, int M, int store) { if (N == 0 || M == 0) return 0; if (s1.charAt(N - 1) == s2.charAt(M - 1) && ((store >> (s1.charAt(N - 1) - 'a')) & 1) == 0) { store = (store | (1 << (s1.charAt(N - 1) - 'a'))); return 1 + find(s1, s2, N - 1, M - 1, store); } else return Math.max(find(s1, s2, N - 1, M, store), find(s1, s2, N, M - 1, store)); } // Driver Code public static void main(String args[]) { String s1, s2; s1 = "aabbcc"; s2 = "aabc"; int store = 0; System.out.println(find(s1, s2, s1.length(), s2.length(), store)); }}// This code is contributed by gfgking |
Python3
# python3 program to implement the approach# Function to find lcs# with no repeating characterdef find(s1, s2, N, M, store): if (N == 0 or M == 0): return 0 if (s1[N - 1] == s2[M - 1] and ((store >> (ord(s1[N - 1]) - ord('a'))) & 1) == 0): store = (store | (1 << (ord(s1[N - 1]) - ord('a')))) return 1 + find(s1, s2, N - 1, M - 1, store) else: return max(find(s1, s2, N - 1, M, store), find(s1, s2, N, M - 1, store))# Driver codeif __name__ == "__main__": s1 = "aabbcc" s2 = "aabc" store = 0 print(find(s1, s2, len(s1), len(s2), store))# This code is contributed by rakeshsahni |
C#
// C# program for the above approachusing System;public class GFG{// Function to find lcs// with no repeating characterstatic int find(string s1, string s2, int N, int M, int store){ if (N == 0 || M == 0) return 0; if (s1[N - 1] == s2[M - 1] && ((store >> (s1[N - 1] - 'a')) & 1) == 0) { store = (store | (1 << (s1[N - 1] - 'a'))); return 1 + find(s1, s2, N - 1, M - 1, store); } else return Math.Max(find(s1, s2, N - 1, M, store), find(s1, s2, N, M - 1, store));}// Driver Codepublic static void Main(String[] args){ string s1, s2; s1 = "aabbcc"; s2 = "aabc"; int store = 0; Console.Write(find(s1, s2, s1.Length, s2.Length, store));}}// This code is contributed by code_hunt. |
Javascript
<script> // JavaScript code for the above approach // Function to find lcs // with no repeating character function find(s1, s2, N, M, store) { if (N == 0 || M == 0) return 0; if (s1[N - 1] == s2[M - 1] && ((store >> (s1[N - 1].charCodeAt(0) - 'a'.charCodeAt(0))) & 1) == 0) { store = (store | (1 << (s1[N - 1].charCodeAt(0) - 'a'.charCodeAt(0) ))); return 1 + find(s1, s2, N - 1, M - 1, store); } else return Math.max(find(s1, s2, N - 1, M, store), find(s1, s2, N, M - 1, store)); } // Driver code let s1, s2; s1 = "aabbcc"; s2 = "aabc"; let store = 0; document.write(find(s1, s2, s1.length, s2.length, store)); // This code is contributed by Potta Lokesh </script> |
Output
3
Time Complexity: O(N * 2N) where N is max(size of s1, size of s2).
Auxiliary Space: O(1)
Efficient approach: An efficient approach is to use memoization to reduce the time complexity. Create a 2D dp[][] array where dp[i][j] stores the length of the longest common subsequence with no repeating character till ith index of s1 and jth index of s2 is considered. If characters at s1[i] and s2[j] are same then dp[i][j] = dp[i-1][j-1] + 1, otherwise dp[i][j] = max(dp[i-1][j], dp[i][j-1]). Just keep track of repeating characters as mentioned in the above approach along with this.
Note: In the implementation, the dp array is implemented using map where the key is the concatenated string of i and j.
Given below is the implementation of the above approach.
C++
// C++ program to implement the approach#include <bits/stdc++.h>using namespace std;// Map for memoizationmap<string, int> mp;// Function to find lcs// with no repeating characterint find(string s1, string s2, int N, int M, long long store){ if (N == 0 || M == 0) return 0; string temp = to_string(N) + '#' + to_string(M) + '#' + to_string(store); if (mp.find(temp) != mp.end()) return mp[temp]; // If the characters are same if (s1[N - 1] == s2[M - 1] && ((store >> (s1[N - 1] - 'a')) & 1) == 0) { store = (store | (1 << (s1[N - 1] - 'a'))); return mp[temp] = 1 + find(s1, s2, N - 1, M - 1, store); } // if the characters are different else return mp[temp] = max(find(s1, s2, N - 1, M, store), find(s1, s2, N, M - 1, store));}// Driver codeint main(){ string s1, s2; s1 = "aabbcc"; s2 = "aabc"; long long store = 0; cout << find(s1, s2, s1.length(), s2.length(), store); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG { // Map for memoization private static HashMap<String, Integer> mp = new HashMap<>(); // Function to find lcs // with no repeating character static int find(String s1, String s2, int N, int M,int store) { if (N == 0 || M == 0) return 0; String temp = String.valueOf(N) + '#' + String.valueOf(M) + '#' + String.valueOf(store); if (mp.containsKey(temp)) return mp.get(temp); // If the characters are same if (s1.charAt(N - 1) == s2.charAt(M - 1) && ((store >> (s1.charAt(N - 1) - 'a')) & 1) == 0) { store = (store | (1 << (s1.charAt(N - 1)- 'a'))); mp.put(temp,1 + find(s1, s2, N - 1,M - 1, store)); return mp.get(temp); } // if the characters are different else { mp.put(temp,Math.max(find(s1, s2, N - 1, M, store), find(s1, s2, N, M - 1, store))); return mp.get(temp); } } // Driver Code public static void main(String args[]) { String s1, s2; s1 = "aabbcc"; s2 = "aabc"; int store = 0; System.out.println(find(s1, s2, s1.length(), s2.length(), store)); }}// This code is contributed by Pushpesh Raj |
Python3
# Python3 program to implement the approach# Map for memoizationmp = {}# Function to find lcs# with no repeating characterdef find(s1,s2,N,M,store): if (N == 0 or M == 0): return 0 temp = str(N) + '#' + str(M) + '#' + str(store) if(temp in mp): return mp[temp] # If the characters are same if (s1[N - 1] == s2[M - 1] and ((store >> (ord(s1[N - 1]) - ord('a'))) & 1)== 0): store = (store | (1 << (ord(s1[N - 1]) - ord('a')))) mp[temp] = 1 + find(s1, s2, N - 1,M - 1, store) return mp[temp] # if the characters are different else: mp[temp] = max(find(s1, s2, N - 1,M, store),find(s1, s2, N, M - 1,store)) return mp[temp]# Driver codes1 = "aabbcc"s2 = "aabc"store = 0print(find(s1, s2, len(s1),len(s2), store))# This code is contributed by shinjanpatra |
C#
// C# program to implement the approachusing System;using System.Collections;using System.Collections.Generic;class GFG { // Map for memoization static Dictionary<string, int> mp = new Dictionary<string, int>(); // Function to find lcs // with no repeating character static int find(string s1, string s2, int N, int M, long store) { if (N == 0 || M == 0) return 0; string temp = N.ToString() + '#' + M.ToString() + '#' + store.ToString(); if (mp.ContainsKey(temp)) { return mp[temp]; } // If the characters are same if (s1[N - 1] == s2[M - 1] && ((store >> (s1[N - 1] - 'a')) & 1) == 0) { store = (store | (1 << (s1[N - 1] - 'a'))); return mp[temp] = 1 + find(s1, s2, N - 1, M - 1, store); } // if the characters are different else return mp[temp] = Math.Max(find(s1, s2, N - 1, M, store), find(s1, s2, N, M - 1, store)); } // Driver code public static void Main() { string s1 = "aabbcc"; string s2 = "aabc"; long store = 0; Console.Write( find(s1, s2, s1.Length, s2.Length, store)); }}// This code is contributed by Samim Hossain Mondal. |
Javascript
<script>// JavaScript program to implement the approach// Map for memoizationlet mp = new Map();// Function to find lcs// with no repeating characterfunction find(s1, s2, N, M,store){ if (N == 0 || M == 0) return 0; let temp = N.toString() + '#' + M.toString() + '#' + store.toString(); if (mp.has(temp)) return mp.get(temp); // If the characters are same if (s1[N - 1] == s2[M - 1] && ((store >> (s1.charCodeAt(N - 1) - 97)) & 1) == 0) { store = (store | (1 << (s1.charCodeAt(N - 1) - 97))); mp.set(temp,1 + find(s1, s2, N - 1,M - 1, store)); return mp.get(temp); } // if the characters are different else{ mp.set(temp,Math.max(find(s1, s2, N - 1,M, store),find(s1, s2, N, M - 1,store))); return mp.get(temp); }}// Driver codelet s1 = "aabbcc";let s2 = "aabc";let store = 0;document.write(find(s1, s2, s1.length, s2.length, store));// code is contributed by shinjanpatra</script> |
Output
3
Time Complexity: O(N * M) where N is the size of s1 and M is the size of s2
Auxiliary Space: O(N * M)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
