PROBLEM LINK:
Author: Swaraj Shelavale
Tester: Ram Agrawal
Editorialist: Yogesh Deolalkar
DIFFICULTY:
MEDIUM.
PREREQUISITES:
Sliding Window, String, Math
PROBLEM:
Chef is hungry, so he went to a market that has a single row of N Cakeshops arranged from left to right. Every Cakeshop has some cakes.
Chef wants to buy as many cakes as possible. However, the Cake Shop
owners has some strict rules that Chef must follow:
- You only have two bags and each bag can only hold a single type of cake. There is no limit on the amount of cake each bag can hold.
- Starting from any Shop of your choice, you must buy exactly one cake from every shop (including the start shop) while moving to the right. The bought cake must fit in one of your bags.
- Once you reach a shop with cake that cannot fit in your bag, you must stop.
Given the type of cake shops have, help Chef find the maximum number of Cakes he can buy.
EXPLANATION:
This problem follows the Sliding Window pattern and is quite similar to Longest Substring with K Distinct Characters. In this problem, we need to find the length of the longest subarray with no more than two distinct integers (or cake types!). This transforms the current problem into Longest Substring with K Distinct Characters where K=2.
SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
#define int long long
#define fast ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
using namespace std;
void solve()
{
int n;
cin>>n;
int arr[n];
for (int i = 0; i < n; i++)
{
cin>>arr[i];
}
int i=0,j=0;
map<int,int>mp;
int maxi = INT_MIN;
while (j<n)
{
mp[arr[j]]++;
if(mp.size() <= 2){
// cout<<mp.size()<<endl;
maxi = max(maxi,j-i+1);
j++;
}else{
mp[arr[i]]â;
if(mp[arr[i]] == 0){
mp.erase(arr[i]);
}
i++;
j++;
}
}
if(maxi == INT_MIN){
cout<<n<<endl;
}else{
cout<<maxi<<endl;
}
}
signed main(){
fast;
int t;
cin>>t;
while(tâ){
solve();
}
return 0;
}