Algorithm to Find the Longest Anagram Subsequence

Given two lowercase alphabet strings a and b, return the length of the longest anagram subsequence.

Constraints
n ≤ 100,000 where n is the length of a
m ≤ 100,000 where m is the length of b
Example 1
Input
a = “afbc”
b = “cxba”
Output
3
Explanation
“abc” is a subsequence in “afbc”
“cba” is a subsequence in “cxba”
And abc and cba are anagrams of each other.

Hints:
Is Subsequence word needed?
try to compare the frequencies.

Longest Anagram Subsequence Algorithm

The subsequence doesn’t matter here because anagram does not need to be in order. We can use two hash maps to count the frequencies for each letter in two strings. If there are 2 ‘a’ in the first string, and 1 ‘a’ in the second string, then we can make an anagram with 1 a.

Going through one dictionary of item/frequencies pair, we can find corresponding frequency of the same item in another string, then update the longest anagram subsequence with the minimum frequency of both.

In C++, we use unordered_map to count the frequencies.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

int longestAnagramSubsequence(string a, string b) {
    unordered_map<char, int> aa, bb;
    for (auto &n: a) {
        aa[n] ++;
    }
    for (auto &n: b) {
        bb[n] ++;
    }
    int ans = 0;
    for (auto &[x, y]: aa) {
        ans += min(y, bb[x]);
    }
    return ans;
}

int longestAnagramSubsequence(string a, string b) {
    unordered_map<char, int> aa, bb;
    for (auto &n: a) {
        aa[n] ++;
    }
    for (auto &n: b) {
        bb[n] ++;
    }
    int ans = 0;
    for (auto &[x, y]: aa) {
        ans += min(y, bb[x]);
    }
    return ans;
}

In Python, we can make implementation simpler by using the Counter object.

1
2
3
4
5
6
7
8

class Solution:
    def longestAnagramSubsequence(self, a, b):
        aa = Counter(a)
        bb = Counter(b)
        ans = 0
        for i in aa:
            ans += min(aa[i], bb[i])
        return ans

class Solution:
    def longestAnagramSubsequence(self, a, b):
        aa = Counter(a)
        bb = Counter(b)
        ans = 0
        for i in aa:
            ans += min(aa[i], bb[i])
        return ans

Both implementations have time complexity O(N+M) where N is the number of characters in string a and M is the number of characters in string b. The space complexity is O(N+M) as we need to use two hash maps.

–EOF (The Ultimate Computing & Technology Blog) —