Equal 0,1,2 - this is hashmap question can you help me with its approach using dry run

#1

Given a string which consists of only 0, 1 or 2s, count the number of substring which have equal number of 0s, 1s and 2s.

Examples:

Input : str = “0102010”
Output : 2
Explanation : Substring str[2, 4] = “102” and
substring str[4, 6] = “201” has
equal number of 0, 1 and 2

Input : str = “102100211”
Output : 5

Input:

The first line of input contains a single integer T denoting the number of test cases. Then T test cases follow. Each test case consists of one line. The line contains a string of 0’s, 1’s and 2’s.

Output:

Corresponding to each test case, in a new line, print the count all possible substrings that have same number of 0s, 1s and 2s.

Constraints:

1 ≤ T ≤ 100
1 ≤ string length ≤ 1000

Example:

Input
2
0102010
102100211

Output
2
5

#2

Hi Affan
I have seen your doubt and am working on the implementation and will post it soon

#3

To solve this question using hashmap, we need to keep track of the counts of 0,1,2 in a substring from index 0 to index i. This i will be iterated over from 0 to size of the string.
This is being done so that each element of the string , we know how many 0,1,2 have occurred previously in the string. This will be used in further operations as explained below.

Let the three arrays that store the count of 0,1,2 be z[],o[],t[] respectively. Now for any substring [i,j] of the string to have equal number of 0,1,2 we must have
z[j] - z[i] = o[j] - [i] = t[j] - t[i]
This equation can be looped over the string, where at each index i we will calculate this difference and check how many times it has occurred previously (this is where map is used for faster access : we keep a key value pair of difference : count in the map and search via difference how may times this difference has been found previously in the string) and update this count to our result. Finally over fully iterating over the display we can display the result.
The time complexity of this solution is O(nlogn) as it takes O(n) to iterate over the array, and each update/search in the map takes O(logn).

#4

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.

#5

I understood how i will iterate but what about j. How do we choose how to iterate j(end of substring).
Please explain using dry run of code

#6

j will be a nested loop inside i running from i to n-1. Basically you are checking all substring combinations possible and using the fast access of hashmap to see if the counts of 0,1,2 have occured before or not. Then adding it to your result. Rest algorithm is same as explained above.

#7

Won’t it result to O(n^2) complexity then

#8

yes it will Time complexity will be O(n^2logn). Sorry for the typo earlier