Number of substrings with each character occurring even times

Number of substrings with each character occurring even times

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 = “geeksforgeeks”
Output: 2

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:

Python3

def subString(s, n):                  count = 0             for i in range(n):                           for len in range(i + 1, n + 1):                                                    test_str = (s[i: len])                             res = {}                             for keys in test_str:                 res[keys] = res.get(keys, 0) + 1                                flag = 0                                         for keys in res:                                                                    if res[keys] % 2 != 0:                        flag = 1                     break                                                 if flag == 0:                 count += 1             return count          S = "abbaa" N = len(S) print(subString(S, N))

Time Complexity: O(N² * 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:

Python3

def subString(s, n):             hash = {0: 1}             pre = 0                  count = 0             for i in s:                           pre ^= (1 << ord(i) - 97)                     count += hash.get(pre, 0)                     hash[pre] = hash.get(pre, 0) + 1                     return count          S = "abbaa" N = len(S) print(subString(S, N))

Time Complexity: O(N)
Auxiliary Space: O(N)

Attention reader! Don’t stop learning now. Get hold of all the important mathematical concepts for competitive programming with the Essential Maths for CP Course at a student-friendly price. To complete your preparation from learning a language to DS Algo and many more,  please refer Complete Interview Preparation Course.

Let's block ads! (Why?)

Original page link

Best Cool Tech Gadgets

Top favorite technology gadgets