0 like 0 dislike
4,904 views

retagged | 4,904 views 0 like 0 dislike
``````You are the guard of a shop. Each time a person enters you not this informations.
You are given information of people leaving and entering shop in the form of binary string.

if s[i] == '1' it means person is entering
if s[i] == '0' it means person is leaving

It is given that a person can enter or leave the shop any number of times.

Using the given info , find minimum possible distinct people you might have seen.

Constraints
1<=len(s)<=10^5

Sample Testcases --

Input-1: 000
Output : 3
Reason : Suppose at t=1, person1 leaves. Then at t=2 , person2 leaves. Then at t=3, Person 3 leaves.
Thus you saw 3 distinct persons leaving the shop

Input-2 : 110011
Output : 2
Reason : At t=1, person1 enters and at t=2 person2 enters the shop . At t=3 , person1 leaves, At t=4, person2 leaves . At t=5, person1 again enters. At t=6, person2 enter the shop again . Thus the minimum number of distinct person is 2.

Input-3: 10101
Output : 1
Reason : At t=1, Person1 enters the shop. At t=2, person 1 leaves . At, t=3 person1  enters. At t=4, person1 leaves.
At t=5, person1 enters . The minimum number of distinct person seens are 1. ``````

C++ Code :

```#include <bits/stdc++.h>
using namespace std;
typedef long long int ll ;
int main()
{
ll one = 0 ;
ll zero = 0 ;
string s ;
cin>>s ;
int i = 0 ;
while(i<s.size())
{
if(s[i]=='1')
{
ll k = zero;
if(k>=1)
{
zero--;
one++;
}
else
{
one++;
}
}
else
{
ll k = one;
if(k>=1)
{
one--;
zero++;
}
else
{
zero++;
}
}
i++;
}
cout<<(one+zero);
return 0;
}```
by Expert (109,630 points)