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
Rationalization: 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
Rationalization: The 2 longest subsequences which are anagrams of each other are “geeks”(0, 3) and “geeks”(8, 12), every of size 5.

Strategy: To unravel the issue observe 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 occasions in a subsequence of anagrams. For instance, if the frequency of a personality is 3, we are able to 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 occasions it may be used. Including the outcome for every character provides us the ultimate reply which is the size of the longest subsequence of anagrams.

Beneath 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 by way of every character within the string S and depend the frequency of every character. 
  • If a personality shouldn’t be 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.

Beneath is the implementation for the above method:

// Program to search out the size of the 2
// longest subsequences within the string that
// are anagrams of one another

#embrace <bits/stdc++.h
utilizing namespace std;

int maxLengthOfAnagramSubsequence(string s)
{

    // Depend the frequency of every
    // character within the string
    int depend[26] = { 0 };
    for (int i = 0; i < s.size(); i++)
        depend[s[i] - 'a']++;

    // Calculate the sum of frequency of
    // every character divided by 2 Spherical
    // right down to the closest integer
    int sum = 0;
    for (int i = 0; i < 26; i++)
        sum += depend[i] / 2;

    // Return the sum as the reply
    return sum;
}

// Drivers code
int most important()
{
    string s = "aabcdabcd";

    // Operate name
    cout << maxLengthOfAnagramSubsequence(s) << endl;
    return 0;
}

// Program to search out the size of the 2 longest subsequences within the string which are anagrams of one another

import java.util.HashMap;
public class GFG {
    public static int longestAnagramSubsequence(String S)
    {
        int maxLength = 0;
        HashMap<Character, Integer> charFrequency
            = new HashMap<>();

        // Depend the frequency of every character within the
        // string
        for (int i = 0; i < S.size(); i++) {
            char c = S.charAt(i);
            charFrequency.put(
                c, charFrequency.getOrDefault(c, 0) + 1);
        }

        // Calculate the sum of frequency of every character
        // divided by 2 Spherical right down to the closest integer
        for (int worth : charFrequency.values()) {
            maxLength += worth / 2;
        }

        // Return the sum as the reply
        return maxLength;
    }

    public static void most important(String[] args)
    {
        String S1 = "aaababcd";
        System.out.println(
            "The size of the 2 longest subsequences of "
            + S1 + " which are anagrams of each other: "
            + longestAnagramSubsequence(S1));
    }
}

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)