Longest subsequence with at least one character appearing in every string
Given a string array arr[], the task is to find the longest subsequence of the array with at least one character appearing in all the strings. Note that all the strings contain only lowercase English alphabets.
Examples:
Input: str = {“ab”, “bc”, “de”}
Output: 2
{“ab”, “bc”} is the required sub-sequence
with ‘b’ as the common character.
Input: str = {“a”, “b”, “c”}
Output: 1
Approach: Create a count[] array such that count[0] will store the number of strings which contain ‘a’, count[1] will store the number of strings that contain ‘b’ and so on…
Now, it’s clear that the answer will be the maximum value from the count[] array. In order to update this array start traversing the string array and for every string, mark which characters are present in the current string in a hash[] array.
And after the traversal, for every character which is present in the current string updates its count in the count[] array.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; #define MAX 26 // Function to return the length of the longest // sub-sequence with at least one // common character in every string int largestSubSeq(string arr[], int n) { // count[0] will store the number of strings // which contain 'a', count[1] will store the // number of strings which contain 'b' and so on.. int count[MAX] = { 0 }; // For every string for ( int i = 0; i < n; i++) { string str = arr[i]; // Hash array to set which character is // present in the current string bool hash[MAX] = { 0 }; for ( int j = 0; j < str.length(); j++) { hash[str[j] - 'a' ] = true ; } for ( int j = 0; j < MAX; j++) { // If current character appears in the // string then update its count if (hash[j]) count[j]++; } } return *(max_element(count, count + MAX)); } // Driver code int main() { string arr[] = { "ab" , "bc" , "de" }; int n = sizeof (arr) / sizeof (string); cout << largestSubSeq(arr, n); return 0; } |
Java
// Java implementation of the approach class GFG { static int MAX = 26 ; // Function to return the length of the longest // sub-sequence with at least one // common character in every string static int largestSubSeq(String arr[], int n) { // count[0] will store the number of strings // which contain 'a', count[1] will store the // number of strings which contain 'b' and so on.. int [] count = new int [MAX]; // For every string for ( int i = 0 ; i < n; i++) { String str = arr[i]; // Hash array to set which character is // present in the current string boolean [] hash = new boolean [MAX]; for ( int j = 0 ; j < str.length(); j++) { hash[str.charAt(j) - 'a' ] = true ; } for ( int j = 0 ; j < MAX; j++) { // If current character appears in the // string then update its count if (hash[j]) count[j]++; } } int max = - 1 ; for ( int i= 0 ;i< MAX; i++) { if (max < count[i]) max = count[i]; } return max; } // Driver code public static void main (String[] args) { String arr[] = { "ab" , "bc" , "de" }; int n = arr.length; System.out.println(largestSubSeq(arr, n)); } } // This code is contributed by ihritik |
Python3
# Python3 implementation of the approach MAX = 26 # Function to return the length of the longest # sub-sequence with at least one # common character in every string def largestSubSeq(arr, n): # count[0] will store the number of strings # which contain 'a', count[1] will store the # number of strings which contain 'b' and so on.. count = [ 0 ] * MAX # For every string for i in range (n): string = arr[i] # Hash array to set which character is # present in the current string _hash = [ False ] * MAX for j in range ( len (string)): _hash[ ord (string[j]) - ord ( 'a' )] = True for j in range ( MAX ): # If current character appears in the # string then update its count if _hash[j] = = True : count[j] + = 1 return max (count) # Driver code if __name__ = = "__main__" : arr = [ "ab" , "bc" , "de" ] n = len (arr) print (largestSubSeq(arr, n)) # This code is contributed by # sanjeev2552 |
C#
// C# implementation of the approach using System; class GFG { static int MAX = 26; // Function to return the length of the longest // sub-sequence with at least one // common character in every string static int largestSubSeq( string [] arr, int n) { // count[0] will store the number of strings // which contain 'a', count[1] will store the // number of strings which contain 'b' and so on.. int [] count = new int [MAX]; // For every string for ( int i = 0; i < n; i++) { string str = arr[i]; // Hash array to set which character is // present in the current string bool [] hash = new bool [MAX]; for ( int j = 0; j < str.Length; j++) { hash[str[j] - 'a' ] = true ; } for ( int j = 0; j < MAX; j++) { // If current character appears in the // string then update its count if (hash[j]) count[j]++; } } int max = -1; for ( int i=0;i< MAX; i++) { if (max < count[i]) max = count[i]; } return max; } // Driver code public static void Main () { string [] arr = { "ab" , "bc" , "de" }; int n = arr.Length; Console.WriteLine(largestSubSeq(arr, n)); } } // This code is contributed by ihritik |
Javascript
<script> // Javascript implementation of the approach var MAX = 26; // Function to return the length of the longest // sub-sequence with at least one // common character in every string function largestSubSeq(arr, n) { // count[0] will store the number of strings // which contain 'a', count[1] will store the // number of strings which contain 'b' and so on.. var count = Array(MAX).fill(0); // For every string for ( var i = 0; i < n; i++) { var str = arr[i]; // Hash array to set which character is // present in the current string var hash = Array(MAX).fill(0); for ( var j = 0; j < str.length; j++) { hash[str[j].charCodeAt(0) - 'a' .charCodeAt(0)] = true ; } for ( var j = 0; j < MAX; j++) { // If current character appears in the // string then update its count if (hash[j]) count[j]++; } } return count.reduce((a,b)=>Math.max(a,b)); } // Driver code var arr = [ "ab" , "bc" , "de" ]; var n = arr.length; document.write( largestSubSeq(arr, n)); </script> |
2
Time Complexity: O(n * l), where n is the size of the given str array and l is the maximum length of a string in the array.
Auxiliary Space: O(26) ? O(1), no extra space is required, so it is a constant.