- Trending Categories
- Data Structure
- Networking
- RDBMS
- Operating System
- Java
- iOS
- HTML
- CSS
- Android
- Python
- C Programming
- C++
- C#
- MongoDB
- MySQL
- Javascript
- PHP

- Selected Reading
- UPSC IAS Exams Notes
- Developer's Best Practices
- Questions and Answers
- Effective Resume Writing
- HR Interview Questions
- Computer Glossary
- Who is Who

We are given string str containing 0’s, 1’s, and 2’s only. The goal is to find all substrings of str that have equal numbers of 0’s 1’s and 2’s. If str is “12012”. Substrings with equal 0’s, 1’s, and 2’s will be “120”, “201” and “012”. The count will be 3.

Let us understand with examples.

**Input** − str=”112200120”

**Output** −Count of Substrings with an equal number of 0s, 1s, and 2s are − 5

**Explanation** − Substrings will be

str[0-5]=”112200”, str[1-6]=”122001”, str[5-7]=”012”, str[6-8]=”120”, str[7-0]=”201”

**Input** − str=”12012”

**Output** −Count of Substrings with an equal number of 0s, 1s, and 2s are: 3

**Explanation** − Substrings will be −

str[0-2]=”120” , str[1-3]=”201”, str[2-4]=”012”

Take a string of integer values and calculate the length of a string

Pass the data to the function for further processing.

Take a temporary variable count to store the count of substrings with equal numbers of 0’s, 1’s, and 2’s.

Create a variable of type map which is mapping the pair to the frequencies of the given numbers.

Store 1 at pair (0,0) and start loop FOR from 0 till the length of a string.

Inside the loop, check IF str[i] = 0 then increment the count for 0’s, ELSE IF str[i] = 1 then increment the count for 1’s, ELSE increment the count for 2’s.

Set 0’s and 1’s to 0’s - 1’s and 0’s and 2’s to 0’s - 2’s.

Make a pair of zero_one and zero_two and set the count as count + map_pair of difference value which is calculated by making the pairs.

Increment the map_pair by 1.

Return count

Print the result.

#include <bits/stdc++.h> using namespace std; int count_string(string str_1, int length_str1, string str_2, int length_str2){ int count = INT_MAX; int arr_1[26] = { 0 }; int arr_2[26] = { 0 }; for (int i = 0; i < length_str1; i++){ arr_1[str_1[i] - 'a']++; } for (int i = 0; i < length_str2; i++){ arr_2[str_2[i] - 'a']++; } int alphabets = 26; for (int i = 0; i < alphabets; i++){ if(arr_2[i]){ count = min(count, arr_1[i] / arr_2[i]); } } return count; } int main(){ string str_1 = "knowledge", str_2 = "know"; int length_str1 = str_1.size(); int length_str2 = str_2.size(); cout<<"Count occurrences of a string that can be constructed from another given string are: "<<count_string(str_1,length_str1, str_2, length_str2); return 0; }

If we run the above code it will generate the following output −

Count of Substrings with equal number of 0s, 1s and 2s are: 1

- Related Questions & Answers
- Largest subarray with equal number of 0s and 1s in C++
- Check if the binary representation of a number has equal number of 0s and 1s in blocks in Python
- Python - List Initialization with alternate 0s and 1s
- Check if an array of 1s and 2s can be divided into 2 parts with equal sum in Python
- XOR counts of 0s and 1s in binary representation in C++
- Print n 0s and m 1s such that no two 0s and no three 1s are together in C Program
- Program to find number of substrings with only 1s using Python
- Encoding a number string into a string of 0s and 1s in JavaScript
- MySQL query to count the number of 0s and 1s from a table column and display them in two columns?
- Count number of substrings with exactly k distinct characters in C++
- Count all 0s which are blocked by 1s in binary matrix in C++
- C Program to construct DFA accepting odd numbers of 0s and 1s
- Construct an NFA accepting strings with an even number of 0s or an odd number of 1s
- Count number of substrings with numeric value greater than X in C++
- Count number of triplets with product equal to given number in C++

Advertisements