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 = “neveropen”
Output: 5
Explanation: The two longest subsequences that are anagrams of one another are “neveropen”(0, 4) and “neveropen”(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:
C++
// Program to find the length of the two// longest subsequences in the string that// are anagrams of each other#include <bits/stdc++.husing namespace std;int maxLengthOfAnagramSubsequence(string s){ // Count the frequency of each // character in the string int count[26] = { 0 }; for (int i = 0; i < s.length(); i++) count[s[i] - 'a']++; // Calculate the sum of frequency of // each character divided by 2 Round // down to the nearest integer int sum = 0; for (int i = 0; i < 26; i++) sum += count[i] / 2; // Return the sum as the answer return sum;}// Drivers codeint main(){ string s = "aabcdabcd"; // Function call cout << maxLengthOfAnagramSubsequence(s) << endl; return 0;} |
Java
// Program to find the length of the two longest subsequences in the string that are anagrams of each otherimport java.util.HashMap;public class GFG { public static int longestAnagramSubsequence(String S) { int maxLength = 0; HashMap<Character, Integer> charFrequency = new HashMap<>(); // Count the frequency of each character in the // string for (int i = 0; i < S.length(); i++) { char c = S.charAt(i); charFrequency.put( c, charFrequency.getOrDefault(c, 0) + 1); } // Calculate the sum of frequency of each character // divided by 2 Round down to the nearest integer for (int value : charFrequency.values()) { maxLength += value / 2; } // Return the sum as the answer return maxLength; } public static void main(String[] args) { String S1 = "aaababcd"; System.out.println( "The length of the two longest subsequences of " + S1 + " that are anagrams of one another: " + longestAnagramSubsequence(S1)); }} |
Python
def maxLengthOfAnagramSubsequence(s): # Count the frequency of each character in the string count = [0] * 26 for i in range(len(s)): count[ord(s[i]) - ord('a')] += 1 # Calculate the sum of frequency of each character divided by 2 # Round down to the nearest integer sum = 0 for i in range(26): sum += count[i] // 2 # Return the sum as the answer return sum# Drivers codes = "aabcdabcd"# Function callprint(maxLengthOfAnagramSubsequence(s)) |
C#
// C# Program to find the length of the two longest// subsequences in the string that are anagrams of each// otherusing System;using System.Collections.Generic;public class GFG { static int longestAnagramSubsequence(string S) { int maxLength = 0; Dictionary<char, int> charFrequency = new Dictionary<char, int>(); // Count the frequency of each character in the // string foreach(char c in S) { if (charFrequency.ContainsKey(c)) { charFrequency++; } else { charFrequency = 1; } } // Calculate the sum of frequency of each character // divided by 2 Round down to the nearest integer foreach(int value in charFrequency.Values) { maxLength += value / 2; } // Return the sum as the answer return maxLength; } static public void Main() { // Code string S1 = "aaababcd"; Console.WriteLine( "The length of the two longest subsequences of " + S1 + " that are anagrams of one another: " + longestAnagramSubsequence(S1)); }}// This code is contributed by sankar. |
Javascript
function maxLengthOfAnagramSubsequence(s) { // Count the frequency of each character in the string const count = new Array(26).fill(0); for (let i = 0; i < s.length; i++) { count[s.charCodeAt(i) - 'a'.charCodeAt(0)]++; } // Calculate the sum of frequency of each character divided by 2 // Round down to the nearest integer let sum = 0; for (let i = 0; i < 26; i++) { sum += Math.floor(count[i] / 2); } // Return the sum as the answer return sum;}// Drivers codeconst s = "aabcdabcd";// Function callconsole.log(maxLengthOfAnagramSubsequence(s)); |
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)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
