Given a string S consisting of N lowercase alphabets, the task is to count the number of substrings whose frequency of each character is even.
Examples:
Input: S = “abbaa”
Output: 4
Explanation:
The substrings having frequency of each character is even are {“abba”, “aa”, “bb”, “bbaa”}.
Therefore, the count is 4.Input: S = “neveropen”
Output: 2
BruteForce Approach :
We can traverse the nested for loops two times to find the ranges of the subarrays and one extra nested for loop for checking that all character is even or not. For more clarity follow the process.
Steps: 1.Run a for loop to traverse the input string. 2.Now we have to find all the ranges possible.For that traverse a nested for loop. 3.In each range for finding the occurrence of even number of character . 4. We can do that by doing xor operation among all the element. 5. If the xor is 0 then all character present in even number of times and increment the counting variable. 6. After traversing all possible rnages Output the cnt.
Implementation of the above approach:
C++
#include <bits/stdc++.h> using namespace std; void findevenone(string s, int n) { int cnt = 0; // Counter variablr // For loop for traversing all the rages for possible // substring for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { int xoro = 0; for (int k = i; k <= j; k++) { xoro ^= s[k]; } if (xoro == 0) cnt++; } } cout << cnt << endl; // Output it return; } signed main() { string str = "abbaa"; // Initialize the string int size = str.size(); cout << "Number of substring with even number of characters is : "; findevenone(str, size); // Calling the function return 0; } |
Java
import java.util.*; public class Main { public static void findevenone(String s, int n) { int cnt = 0; // Counter variable // For loop for traversing all the ranges for // possible substring for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { int xoro = 0; for (int k = i; k <= j; k++) { xoro ^= s.charAt(k); } if (xoro == 0) cnt++; } } System.out.println(cnt); // Output it return; } public static void main(String[] args) { String str = "abbaa"; // Initialize the string int size = str.length(); System.out.print( "Number of substring with even number of characters is : "); findevenone(str, size); // Calling the function } } |
Python3
def findevenone(s: str, n: int) -> None: cnt = 0 # Counter variable # For loop for traversing all the rages for possible # substring for i in range(n): for j in range(i, n): xoro = 0 for k in range(i, j + 1): xoro ^= ord(s[k]) if xoro == 0: cnt += 1 print(cnt) # Output it str = "abbaa" # Initialize the string size = len(str) print("Number of substring with even number of characters is: ", end="") findevenone(str, size) # Calling the function |
C#
using System; class Program { static void findevenone(string s, int n) { int cnt = 0; // Counter variable // For loop for traversing all the rages for // possible substring for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { int xoro = 0; for (int k = i; k <= j; k++) { xoro ^= s[k]; } if (xoro == 0) cnt++; } } Console.WriteLine(cnt); // Output it } static void Main(string[] args) { string str = "abbaa"; // Initialize the string int size = str.Length; Console.Write( "Number of substring with even number of characters is : "); findevenone(str, size); // Calling the function } } |
Javascript
// Define a function to find the number of substrings with an even number of characters function findevenone(s, n) { let cnt = 0; // Counter variable // Nested for loop for traversing all possible substrings for (let i = 0; i < n; i++) { for (let j = i; j < n; j++) { let xoro = 0; // For loop to XOR all characters in the current substring for (let k = i; k <= j; k++) { xoro ^= s.charCodeAt(k); } // Increment counter if the XOR of the substring is zero if (xoro == 0) cnt++; } } console.log("Number of substring with even number of characters is : " + cnt); // Output the result } // Main function function main() { let str = "abbaa"; // Initialize the string let size = str.length; findevenone(str, size); // Call the function to find the number of substrings with even number of characters } // Call the main function main(); |
Output
Number of substring with even number of characters is : 4
Time Complexity :O(N3)
Space Complexity: O(1)
Naive Approach: The simplest approach to solve the given problem is to generate all possible substrings of the given string and count those substrings having even frequency of every character. After checking for all substrings, print the total count obtained.
Below is the implementation of the above approach:
C++
// C++ program for the above approach // Function to count substrings having // even frequency of each character #include<bits/stdc++.h> using namespace std; int subString(string s,int n) { // Stores the total // count of substrings int count = 0; // Traverse the range [0, N]: for(int i = 0; i < n; i++) { // Traverse the range [i + 1, N] for(int len = 1; len <= (n-i); len++) { // Stores the substring over // the range of indices [i, len] string test_str = s.substr(i, len); // Stores the frequency of characters unordered_map<char,int>res; // Count frequency of each character for(auto keys : test_str) res[keys]++; int flag = 0; // Traverse the dictionary for(auto key : res) { // If any of the keys // have odd count if (key.second % 2 != 0) { flag = 1; break; } } // Otherwise if (flag == 0) { count ++; } } } // Return count return count; } // Driver Code int main() { string S = "abbaa"; int N = S.length(); cout<<subString(S,N)<<endl; } // This code is contributed by shinjanpatra |
Java
// Java program for the above approach import java.io.*; import java.lang.*; import java.util.*; public class GFG { // Function to count substrings having // even frequency of each character static int subString(String s, int n) { // Stores the total // count of substrings int count = 0; // Traverse the range [0, N]: for (int i = 0; i < n; i++) { // Traverse the range [i + 1, N] for (int len = i + 1; len <= n; len++) { // Stores the substring over // the range of indices [i, len] String test_str = s.substring(i, len); // Stores the frequency of characters HashMap<Character, Integer> res = new HashMap<>(); // Count frequency of each character for (char keys : test_str.toCharArray()) { res.put(keys, res.getOrDefault(keys, 0) + 1); } int flag = 0; // Traverse the dictionary for (char keys : res.keySet()) { // If any of the keys // have odd count if (res.get(keys) % 2 != 0) { flag = 1; break; } } // Otherwise if (flag == 0) count += 1; } } // Return count return count; } // Driver Code public static void main(String[] args) { String S = "abbaa"; int N = S.length(); System.out.println(subString(S, N)); } } // This code is contributed by Kingash. |
Python3
# Python program for the above approach # Function to count substrings having # even frequency of each character def subString(s, n): # Stores the total # count of substrings count = 0 # Traverse the range [0, N]: for i in range(n): # Traverse the range [i + 1, N] for len in range(i + 1, n + 1): # Stores the substring over # the range of indices [i, len] test_str = (s[i: len]) # Stores the frequency of characters res = {} # Count frequency of each character for keys in test_str: res[keys] = res.get(keys, 0) + 1 flag = 0 # Traverse the dictionary for keys in res: # If any of the keys # have odd count if res[keys] % 2 != 0: flag = 1 break # Otherwise if flag == 0: count += 1 # Return count return count # Driver Code S = "abbaa"N = len(S) print(subString(S, N)) |
C#
// C# program for the above approach using System; using System.Collections.Generic; public class GFG{ // Function to count substrings having // even frequency of each character static int subString(string s, int n) { // Stores the total // count of substrings int count = 0; // Traverse the range [0, N]: for (int i = 0; i < n; i++) { // Traverse the range [i + 1, N] for (int len = i + 1; len <= n; len++) { // Stores the substring over // the range of indices [i, len] string test_str = s.Substring(i, len-i); // Stores the frequency of characters Dictionary<char,int> res = new Dictionary<char,int>(); // Count frequency of each character foreach (char keys in test_str.ToCharArray()) { if(!res.ContainsKey(keys)) res.Add(keys,0); res[keys]++; } int flag = 0; // Traverse the dictionary foreach (KeyValuePair<char,int> keys in res) { // If any of the keys // have odd count if (keys.Value % 2 != 0) { flag = 1; break; } } // Otherwise if (flag == 0) count += 1; } } // Return count return count; } // Driver Code static public void Main (){ string S = "abbaa"; int N = S.Length; Console.WriteLine(subString(S, N)); } } // This code is contributed by rag2127. |
Javascript
<script> // JavaScript program for the above approach // Function to count substrings having // even frequency of each character function subString(s, n) { // Stores the total // count of substrings var count = 0; // Traverse the range [0, N]: for(var i = 0; i < n; i++) { // Traverse the range [i + 1, N] for(var len = i + 1; len <= n; len++) { // Stores the substring over // the range of indices [i, len] var test_str = s.substring(i, len); // Stores the frequency of characters var res = {}; // Count frequency of each character var temp = test_str.split(""); for(const keys of temp) { res[keys] = (res[keys] ? res[keys] : 0) + 1; } var flag = 0; // Traverse the dictionary for(const [key, value] of Object.entries(res)) { // If any of the keys // have odd count if (res[key] % 2 != 0) { flag = 1; break; } } // Otherwise if (flag == 0) count += 1; } } // Return count return count; } // Driver Code var S = "abbaa"; var N = S.length; document.write(subString(S, N)); // This code is contributed by rdtank </script> |
Output
4
Time Complexity: O(N2 * 26)
Auxiliary Space: O(N)
Efficient Approach: The above approach can be optimized by using the concept of Bitmasking and dictionary. Follow the below steps to solve the problem:
- Initialize a dictionary, say hash to store the count of a character.
- Initialize two variables, say count as 0 and pre as 0 to store the total count of substrings having an even count of each character and to store the mask of characters included in the substring.
- Traverse the given string and perform the following steps:
- Flip the (S[i] – ‘a’)th bit in the variable pre.
- Increment the count by hash[pre] and the count of pre in the hash.
- After completing the above steps, print the value of count as the result.
Below is the implementation of the above approach:
C++
// C ++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to count substrings having // even frequency of each character int subString(string s, int n) { // Stores the count of a character map<int, int> hash; hash[0] = 1; // Stores bitmask int pre = 0; // Stores the count of substrings // with even count of each character int count = 0; // Traverse the string S for (int i = 0; i < n; i++) { // Flip the ord(i)-97 bits in pre pre ^= (1 << int(s[i]) - 97); // Increment the count by hash[pre] count += hash[pre]; // Increment count of pre in hash hash[pre] = hash[pre] + 1; } // Return the total count obtained return count; } // Driver Code int main() { string S = "abbaa"; int N = S.length(); cout << (subString(S, N)); } // THIS CODE IS CONTRIBUTED BY UKASP. |
Java
// Java program for the above approach import java.util.*; import java.lang.*; class GFG{ // Function to count substrings having // even frequency of each character static int subString(String s, int n) { // Stores the count of a character Map<Integer, Integer> hash = new HashMap<>(); hash.put(0, 1); // Stores bitmask int pre = 0; // Stores the count of substrings // with even count of each character int count = 0; // Traverse the string S for(int i = 0; i < n; i++) { // Flip the ord(i)-97 bits in pre pre ^= (1 << (int)(s.charAt(i) - 97)); // Increment the count by hash[pre] count += hash.getOrDefault(pre, 0); // Increment count of pre in hash hash.put(pre, hash.getOrDefault(pre, 0) + 1); } // Return the total count obtained return count; } // Driver code public static void main(String[] args) { String S = "abbaa"; int N = S.length(); System.out.print(subString(S, N)); } } // This code is contributed by offbeat |
Python3
# Python program for the above approach # Function to count substrings having # even frequency of each character def subString(s, n): # Stores the count of a character hash = {0: 1} # Stores bitmask pre = 0 # Stores the count of substrings # with even count of each character count = 0 # Traverse the string S for i in s: # Flip the ord(i)-97 bits in pre pre ^= (1 << ord(i) - 97) # Increment the count by hash[pre] count += hash.get(pre, 0) # Increment count of pre in hash hash[pre] = hash.get(pre, 0) + 1 # Return the total count obtained return count # Driver Code S = "abbaa"N = len(S) print(subString(S, N)) |
C#
// C# program for the above approach using System.IO; using System; using System.Collections.Generic; class GFG{ // Function to count substrings having // even frequency of each character static int subString(string s, int n) { // Stores the count of a character Dictionary<int, int> hash = new Dictionary<int, int>(); hash[0] = 1; // Stores bitmask int pre = 0; // Stores the count of substrings // with even count of each character int count = 0; // Traverse the string S for(int i = 0; i < n; i++) { // Flip the ord(i)-97 bits in pre pre ^= (1 << (int)(s[i]) - 97); // Increment the count by hash[pre] if (hash.ContainsKey(pre)) count += hash[pre]; else count += 0; // Increment count of pre in hash if (hash.ContainsKey(pre)) hash[pre] = hash[pre] + 1; else hash.Add(pre, 1); } // Return the total count obtained return count; } // Driver code static void Main() { String S = "abbaa"; int N = S.Length; Console.WriteLine(subString(S, N)); } } // This code is contributed by sk944795 |
Javascript
<script> // JavaScript program for the above approach // Function to count substrings having // even frequency of each character function subString(s,n) { // Stores the count of a character let hash = new Map(); hash.set(0, 1); // Stores bitmask let pre = 0; // Stores the count of substrings // with even count of each character let count = 0; // Traverse the string S for(let i = 0; i < n; i++) { // Flip the ord(i)-97 bits in pre pre ^= (1 << s[i].charCodeAt(0) - 97); if(!hash.has(pre)) hash.set(pre,0); // Increment the count by hash[pre] count += (hash.get(pre)); // Increment count of pre in hash hash.set(pre, hash.get(pre)==null? 0 : hash.get(pre)+1); } // Return the total count obtained return count; } // Driver code let S = "abbaa"; let N = S.length; document.write(subString(S, N)); // This code is contributed by avanitrachhadiya2155 </script> |
Output:
4
Time Complexity: O(N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
