Longest subsequence with at least one character appearing in every string
Last Updated :
21 Dec, 2022
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++
#include <bits/stdc++.h>
using namespace std;
#define MAX 26
int largestSubSeq(string arr[], int n)
{
int count[MAX] = { 0 };
for (int i = 0; i < n; i++) {
string str = arr[i];
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 (hash[j])
count[j]++;
}
}
return *(max_element(count, count + MAX));
}
int main()
{
string arr[] = { "ab", "bc", "de" };
int n = sizeof(arr) / sizeof(string);
cout << largestSubSeq(arr, n);
return 0;
}
|
Java
class GFG
{
static int MAX = 26;
static int largestSubSeq(String arr[], int n)
{
int [] count = new int[MAX];
for (int i = 0; i < n; i++) {
String str = arr[i];
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 (hash[j])
count[j]++;
}
}
int max = -1;
for(int i=0;i< MAX; i++)
{
if(max < count[i])
max = count[i];
}
return max;
}
public static void main (String[] args)
{
String arr[] = { "ab", "bc", "de" };
int n = arr.length;
System.out.println(largestSubSeq(arr, n));
}
}
|
Python3
MAX = 26
def largestSubSeq(arr, n):
count = [0] * MAX
for i in range(n):
string = arr[i]
_hash = [False] * MAX
for j in range(len(string)):
_hash[ord(string[j]) - ord('a')] = True
for j in range(MAX):
if _hash[j] == True:
count[j] += 1
return max(count)
if __name__ == "__main__":
arr = [ "ab", "bc", "de" ]
n = len(arr)
print(largestSubSeq(arr, n))
|
C#
using System;
class GFG
{
static int MAX = 26;
static int largestSubSeq(string [] arr, int n)
{
int [] count = new int[MAX];
for (int i = 0; i < n; i++)
{
string str = arr[i];
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 (hash[j])
count[j]++;
}
}
int max = -1;
for(int i=0;i< MAX; i++)
{
if(max < count[i])
max = count[i];
}
return max;
}
public static void Main ()
{
string [] arr = { "ab", "bc", "de" };
int n = arr.Length;
Console.WriteLine(largestSubSeq(arr, n));
}
}
|
Javascript
<script>
var MAX = 26;
function largestSubSeq(arr, n)
{
var count = Array(MAX).fill(0);
for (var i = 0; i < n; i++) {
var str = arr[i];
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 (hash[j])
count[j]++;
}
}
return count.reduce((a,b)=>Math.max(a,b));
}
var arr = ["ab", "bc", "de" ];
var n = arr.length;
document.write( largestSubSeq(arr, n));
</script>
|
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.
Like Article
Suggest improvement
Share your thoughts in the comments
Please Login to comment...