Longest Common Subsequence with Permutations

Problem Statement

In the “Longest Common Subsequence with Permutations” problem we have given two strings “s” and “t”. Find the longest string whose permutations are sub-sequences of the given two strings. Output longest must be sorted.

Input Format

The first line containing a string “s”.

The second line containing a string “t”.

Output Format

The first line only containing a string that represents the longest string whose permutations are sub-sequences of the strings “s” and “t”.

Example

hello
hole

ehlo

Explanation: Here, the permutation of “ehlo” is the subsequence of hello, hole which is sorted and longest among all possible permutations.

Algorithm

1. Create two arrays count1 and count2.

2. Count1 stores the count of characters in string1 and count2 stores the count of characters in string2.

3. Append character ‘c’ by min(count1[‘c’], count2[‘c’]) times into the result.

4. Do this for all characters in lexicographic order.

5. Return the final result.

Implementation

C++ Program to find the Longest Common Subsequence with Permutations

#include <bits/stdc++.h>
using namespace std;
 
int main()
{
    string s,t;
    cin>>s>>t;
    int count1[26] = {0};
    int count2[26] = {0};
    for (int i=0; i<s.length(); i++)
    {
        count1[s[i]-'a']++;
    }
    for (int i=0; i<t.length(); i++)
    {
        count2[t[i]-'a']++;
    }
    string ans;
    for(int i=0; i<26; i++)
    {
        for (int j=1;j<=min(count1[i],count2[i]); j++)
        {
            ans.push_back('a' + i);
        }
    }
    cout<<ans<<endl;
    return 0;
}

Java Program to find the Longest Common Subsequence with Permutations

import java.util.Scanner;

class sum
{
    public static void main(String[] args)
    {
        Scanner sr = new Scanner(System.in);
        String s = sr.next();
        String t = sr.next();
        int count1[] = new int[26];
        int count2[] = new int[26];
        for(int i=0;i<26;i++)
        {
            count1[i]=0;
            count2[i]=0;
        }
        for (int i=0; i<s.length(); i++)
        {
            count1[s.charAt(i)-'a']++;
        }
        for (int i=0; i<t.length(); i++)
        {
            count2[t.charAt(i)-'a']++;
        }
        String ans="";
        for(int i=0; i<26; i++)
        {
            for (int j=1;j<=Math.min(count1[i],count2[i]); j++)
            {
                ans+=(char)('a' + i);
            }
        }
        System.out.println(ans);
    }
}

tutorialcup
algorithm

ailort

Complexity Analysis to find the Longest Common Subsequence with Permutations

Time Complexity

O(n) where n is denoting the length of the maximum size string among “s” and “t”.

Space Complexity

O(n) because we store the final answer in a string. And the maximum length of the string is equal to n if both the string are equals.