Question

Hackwithinfyi | Infosys | OA Coding Questions and Solutions | Set - 1 | 2022

Answer 1

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;
}