Find length of the longest non-intersecting anagram Subsequence – GeeksforGeeks

Given a string S of length N, find the length of the two longest non-intersecting subsequences in S that are anagrams of each other.

Input: S = “aaababcd”
Output: 3
Explanation: Index of characters in the 2 subsequences are:

• {0, 1, 3} = {a, a, b} 
• {2, 4, 5} = {a, a, b} 

The above two subsequences of S are anagrams.

• Frequency of ‘a’ = 4, so 2 ‘a’s can be used in both the anagrams.
• Frequency of ‘b’ = 2, so 1 ‘a’ can be used in both the anagrams.

Hence 2 + 1 = 3 is the length of two longest subsequence in S that are anagrams of each other.

Input: S = “geeksforgeeks”
Output: 5
Explanation: The two longest subsequences that are anagrams of one another are “geeks”(0, 3) and “geeks”(8, 12), each of length 5.

Approach: To solve the problem follow the below idea:

The approach calculates the maximum length of a subsequence of anagrams by dividing each character frequency by 2 and taking the floor. This is because each character can appear at most 2 times in a subsequence of anagrams. For example, if the frequency of a character is 3, we can use 2 of those in a subsequence of anagrams. Hence, we take the floor of half of its frequency to get the maximum number of times it can be used. Adding the result for each character gives us the final answer which is the length of the longest subsequence of anagrams.

Below are the steps for the above approach:

• Initialize an array count[] to store the frequency of each character in the string S.
• Then, we loop through each character in the string S and count the frequency of each character. 
  • If a character is not in the count[] array, we set its frequency to 1. 
  • If a character already exists in the count[] array, we increment its frequency by 1.
• Iterate the array count[] and divide each value i.e the frequency of each character by 2 and take the floor value and add the variable sum to get the maximum length of the two longest subsequences of S that are anagrams of one another.

Below is the implementation for the above approach:

The length of the two longest subsequences of aaababcd that are anagrams of one another: 3

Time Complexity: O(N), where N is the length of the string.
Auxiliary Space: O(1)