Given a binary string str. The task is to find the size of the set(contains unique substrings) of substrings such that if there is a substring(suppose A) of length n with an even number of 1’s and also there is another substring (suppose B) of the same length n and even number of 1’s and it is reverse of A, then only A would be considered in the set of strings.
Examples:
Input: str = “10101”
Output: 8
Explanation: All unique substrings of given string={1, 0, 10, 01, 101, 010, 1010, 0101, 10101}.
In the above set (1010, 0101) is following the special property.
Therefore, only 1010 will be considered in the given set.
Updated Set = A = {1, 0, 10, 01, 101, 010, 1010, 10101}.
Length of A=8Input: str = “10001”
Output: 11
Explanation: All unique substrings of given string={1, 0, 10, 01, 00, 100, 000, 001, 1000, 0001, 10001}.
In the above set no string is following the special property. Length of Set=11
Approach: Follow these two particular rules to solve the problem:
- All pairwise strings not following special property should be identified uniquely.
- All pairwise strings following special property should be identified as one.
So to solve this problem, use a set of List of integers where each list would contain three variables: {length, even, odd}. Also, use a count variable that will describe the count of 1’s in the substring. Here ‘length’ will describe the length of the substring. even and odd variables are used to describe the count of 1’s as even or odd whenever ‘0’ is encountered in the substring. After that, add it to the set of substrings and then print the size of the set.
WHY DOES THIS WORK?
Consider a binary string with an even number of 1’s and whenever 0 is encountered in it, see how many 1’s occur in it before that 0 and if it is even increase the even variable count otherwise increase the odd variable count.
Suppose, when 0 is encountered in a substring and till that it has even 1’s then remaining would also be 1’s(because we have considered a string with even 1’s), similarly if we have odd 1’s till whenever we encounter 0 therefore remaining would also be odd 1’s. Therefore the reverse string would have the same parity(i.e count of 1’s as even or odd). That’s why it would not take the reverse string into consideration.
Follow the steps below to solve the problem:
- Initialize the HashSet s[].
- Iterate over the range [0, str.length()) using the variable i and perform the following tasks:
- Initialize the variables count, even and odd as 0.
- Iterate over the range [0, a.length()) using the variable j and perform the following tasks:
- If str[j] equals 1, then increase the value of count by 1.
- Else, if count%2 equals 0 then increase the value of even by 1 else the value of odd by 1.
- Initialize the variable len as j-i+1.
- Initialize a new ArrayList x[].
- Add the values of {len, even, odd} to the ArrayList x[].
- Add x[] to the HashSet s[].
- After performing the above steps, print the value of the size of the set as the answer.
Below is the implementation of the above approach.
C++
// C++ code for the above approach#include <bits/stdc++.h>using namespace std;// Function to find number of substrings// fulfilling the conditionvoid find(string a){ // Initialize the hash-set set<vector<int>> s; // Traverse the string for (int i = 0; i < a.length(); i++) { // Initialize the variables int count = 0, even = 0, odd = 0; for (int j = i; j < a.length(); j++) { // Check the condition if (a[j] == '1') { count++; } else { if (count % 2 == 0) { even++; } else { odd++; } } int len = j - i + 1; vector<int> x; x.push_back(len); x.push_back(even); x.push_back(odd); s.insert(x); } } // Print the result cout << (s.size());}// Driver Codeint main(){ string str = "10101"; find(str); return 0;}// This code is contributed by Potta Lokesh |
Java
// Java code to implement above approachimport java.io.*;import java.util.*;class GFG { // Function to find number of substrings // fulfilling the condition public static void find(String a) { // Initialize the hash-set HashSet<ArrayList<Integer> > s = new HashSet<>(); // Traverse the string for (int i = 0; i < a.length(); i++) { // Initialize the variables int count = 0, even = 0, odd = 0; for (int j = i; j < a.length(); j++) { // Check the condition if (a.charAt(j) == '1') { count++; } else { if (count % 2 == 0) { even++; } else { odd++; } } int len = j - i + 1; ArrayList<Integer> x = new ArrayList<>(); x.add(len); x.add(even); x.add(odd); s.add(x); } } // Print the result System.out.println(s.size()); } // Driver Code public static void main(String[] args) { String str = "10101"; find(str); }} |
Python3
# Python code to implement above approach# Function to find number of substrings# fulfilling the conditiondef find(a): # Initialize the hash-set s = set(); # Traverse the string for i in range(len(a)): # Initialize the variables count = 0; even = 0; odd = 0; for j in range(i,len(a)): # Check the condition if (a[j] == '1'): count += 1; else: if (count % 2 == 0): even += 1; else: odd += 1; length = j - i + 1; x = str(length)+str(even)+str(odd); s.add(x) # Print the result print(len(s));# Driver Codeif __name__ == '__main__': string = "10101"; find(string);# This code is contributed by 29AjayKumar |
C#
// C# code to implement above approachusing System;using System.Collections;using System.Collections.Generic;public class GFG{ // Function to find number of substrings // fulfilling the condition public static void find(String a) { // Initialize the hash-set HashSet<string> s = new HashSet<string>(); string x; // Traverse the string for (int i = 0; i < a.Length; i++) { // Initialize the variables int count = 0, even = 0, odd = 0; for (int j = i; j < a.Length; j++) { // Check the condition if (a[j] == '1') { count++; } else { if (count % 2 == 0) { even++; } else { odd++; } } int len = j - i + 1; x = len.ToString() + even.ToString() +odd.ToString(); s.Add(x); } } // Print the result Console.Write(s.Count); } // Driver Code public static void Main() { string str = "10101"; find(str); }}// This code is contributed by Shubham Singh |
Javascript
<script>// Javascript code to implement above approach// Function to find number of substrings// fulfilling the conditionfunction find(a){ // Initialize the hash-set let s = new Set(); let x = ""; // Traverse the string for (let i = 0; i < a.length; i++) { // Initialize the variables let count = 0, even = 0, odd = 0; for (let j = i; j < a.length; j++) { // Check the condition if (a[j] == '1') { count++; } else { if (count % 2 == 0) { even++; } else { odd++; } } let len = j - i + 1; x = len.toString() + even.toString() + odd.toString(); s.add(x); } } // Print the result document.write(s.size);}// Driver Codelet str = "10101";find(str);// This code is contributed Saurabh Jaiswal</script> |
8
Time Complexity: O(N*N) where N is the length of string
Auxiliary Space: O(N)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
