Discover size of the longest non-intersecting anagram Subsequence

Given a string S of size N, discover the size of the 2 longest non-intersecting subsequences in S which are anagrams of one another.

Enter: S = “aaababcd”
Output: 3
Clarification: Index of characters within 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 utilized in each the anagrams.
• Frequency of ‘b’ = 2, so 1 ‘a’ can be utilized in each the anagrams.

Therefore 2 + 1 = 3 is the size of two longest subsequence in S which are anagrams of one another.

Enter: S = “geeksforgeeks”
Output: 5
Clarification: The 2 longest subsequences which are anagrams of each other are “geeks”(0, 3) and “geeks”(8, 12), every of size 5.

Strategy: To resolve the issue comply with the under concept:

The method calculates the utmost size of a subsequence of anagrams by dividing every character frequency by 2 and taking the ground. It is because every character can seem at most 2 instances in a subsequence of anagrams. For instance, if the frequency of a personality is 3, we will use 2 of these in a subsequence of anagrams. Therefore, we take the ground of half of its frequency to get the utmost variety of instances it may be used. Including the end result for every character provides us the ultimate reply which is the size of the longest subsequence of anagrams.

Under are the steps for the above method:

• Initialize an array depend[] to retailer the frequency of every character within the string S.
• Then, we loop via every character within the string S and depend the frequency of every character. 
  • If a personality just isn’t within the depend[] array, we set its frequency to 1. 
  • If a personality already exists within the depend[] array, we increment its frequency by 1.
• Iterate the array depend[] and divide every worth i.e the frequency of every character by 2 and take the ground worth and add the variable sum to get the utmost size of the 2 longest subsequences of S which are anagrams of each other.

Under is the implementation for the above method:

The size of the 2 longest subsequences of aaababcd which are anagrams of each other: 3

Time Complexity: O(N), the place N is the size of the string.
Auxiliary Area: O(1)