Longest Common Anagram Subsequence
Last Updated :
27 Sep, 2022
Given two strings str1 and str2 of length n1 and n2 respectively. The problem is to find the length of the longest subsequence which is present in both the strings in the form of anagrams.
Note: The strings contain only lowercase letters.
Examples:
Input : str1 = "abdacp", str2 = "ckamb"
Output : 3
Subsequence of str1 = abc
Subsequence of str2 = cab
OR
Subsequence of str1 = bac
Subsequence of str2 = cab
These are longest common anagram subsequences.
Input : str1 = "abbcfke", str2 = "fbaafbly"
Output : 4
Approach: Create two hash tables say freq1 and freq2. Store frequencies of each character of str1 in freq1. Likewise, store frequencies of each character of str2 in freq2. Initialize len = 0. Now, for each lowercase letter finds its lowest frequency from the two hash tables and accumulate it to len.
Implementation:
C++
#include <bits/stdc++.h>
using namespace std;
#define SIZE 26
int longCommonAnagramSubseq(char str1[], char str2[],
int n1, int n2)
{
int freq1[SIZE], freq2[SIZE];
memset(freq1, 0, sizeof(freq1));
memset(freq2, 0, sizeof(freq2));
int len = 0;
for (int i = 0; i < n1; i++)
freq1[str1[i] - 'a']++;
for (int i = 0; i < n2; i++)
freq2[str2[i] - 'a']++;
for (int i = 0; i < SIZE; i++)
len += min(freq1[i], freq2[i]);
return len;
}
int main()
{
char str1[] = "abdacp";
char str2[] = "ckamb";
int n1 = strlen(str1);
int n2 = strlen(str2);
cout << "Length = "
<< longCommonAnagramSubseq(str1, str2, n1, n2);
return 0;
}
|
Java
import java.io.*;
class GFG
{
static int SIZE = 26;
static int longCommonAnagramSubseq(String str1,
String str2,
int n1, int n2)
{
int []freq1 = new int[SIZE];
int []freq2 = new int[SIZE];
for(int i = 0; i < SIZE; i++)
{
freq1[i] = 0;
freq2[i] = 0;
}
int len = 0;
for (int i = 0; i < n1; i++)
freq1[(int)str1.charAt(i) - (int)'a']++;
for (int i = 0; i < n2; i++)
freq2[(int)str2.charAt(i) - (int)'a']++;
for (int i = 0; i < SIZE; i++)
len += Math.min(freq1[i],
freq2[i]);
return len;
}
public static void main(String args[])
{
String str1 = "abdacp";
String str2 = "ckamb";
int n1 = str1.length();
int n2 = str2.length();
System.out.print("Length = " +
longCommonAnagramSubseq(str1, str2,
n1, n2));
}
}
|
Python 3
SIZE = 26
def longCommonAnagramSubseq(str1, str2,
n1, n2):
freq1 = [0] * SIZE
freq2 = [0] * SIZE
l = 0
for i in range(n1):
freq1[ord(str1[i]) -
ord('a')] += 1
for i in range(n2) :
freq2[ord(str2[i]) -
ord('a')] += 1
for i in range(SIZE):
l += min(freq1[i], freq2[i])
return l
if __name__ == "__main__":
str1 = "abdacp"
str2 = "ckamb"
n1 = len(str1)
n2 = len(str2)
print("Length = ",
longCommonAnagramSubseq(str1, str2,
n1, n2))
|
C#
using System;
class GFG
{
static int SIZE = 26;
static int longCommonAnagramSubseq(string str1,
string str2,
int n1, int n2)
{
int []freq1 = new int[SIZE];
int []freq2 = new int[SIZE];
for(int i = 0; i < SIZE; i++)
{
freq1[i] = 0;
freq2[i] = 0;
}
int len = 0;
for (int i = 0; i < n1; i++)
freq1[str1[i] - 'a']++;
for (int i = 0; i < n2; i++)
freq2[str2[i] - 'a']++;
for (int i = 0; i < SIZE; i++)
len += Math.Min(freq1[i],
freq2[i]);
return len;
}
static void Main()
{
string str1 = "abdacp";
string str2 = "ckamb";
int n1 = str1.Length;
int n2 = str2.Length;
Console.Write("Length = " +
longCommonAnagramSubseq(str1, str2,
n1, n2));
}
}
|
PHP
<?php
$SIZE = 26;
function longCommonAnagramSubseq($str1, $str2,
$n1, $n2)
{
global $SIZE;
$freq1 = array();
$freq2 = array();
for($i = 0;
$i < $SIZE; $i++)
{
$freq1[$i] = 0;
$freq2[$i] = 0;
}
$len = 0;
for ($i = 0; $i < $n1; $i++)
$freq1[ord($str1[$i]) -
ord('a')]++;
for ($i = 0; $i < $n2; $i++)
$freq2[ord($str2[$i]) -
ord('a')]++;
for ($i = 0; $i < $SIZE; $i++)
{
$len += min($freq1[$i],
$freq2[$i]);
}
return $len;
}
$str1 = "abdacp";
$str2 = "ckamb";
$n1 = strlen($str1);
$n2 = strlen($str2);
echo ("Length = " .
longCommonAnagramSubseq($str1, $str2,
$n1, $n2));
?>
|
Javascript
<script>
let SIZE = 26;
function longCommonAnagramSubseq(str1,str2,n1,n2)
{
let freq1 = new Array(SIZE);
let freq2 = new Array(SIZE);
for(let i = 0; i < SIZE; i++)
{
freq1[i] = 0;
freq2[i] = 0;
}
let len = 0;
for (let i = 0; i < n1; i++)
freq1[str1[i].charCodeAt(0) - 'a'.charCodeAt(0)]++;
for (let i = 0; i < n2; i++)
freq2[str2[i].charCodeAt(0) - 'a'.charCodeAt(0)]++;
for (let i = 0; i < SIZE; i++)
len += Math.min(freq1[i],
freq2[i]);
return len;
}
let str1 = "abdacp";
let str2 = "ckamb";
let n1 = str1.length;
let n2 = str2.length;
document.write("Length = " +
longCommonAnagramSubseq(str1, str2,
n1, n2));
</script>
|
Time Complexity: O(n+m).
Auxiliary Space: O(1).
Like Article
Suggest improvement
Share your thoughts in the comments
Please Login to comment...