PROBLEM LINK:
Author: vikiwarrior
Tester: hellb0y_suru
Editorialist: vikiwarrior
DIFFICULTY:
EASY
PROBLEM:
Find the maximum length of the substring for a given x,y,z such that all elements in the substring are equal.
EXPLANATION:
This is basically a variable-size sliding window approach.
Let’s suppose we search for the maximum subarray having only 0’s. Later we will do the same for 1’s and 2’s and take the maximum among them as our answer.
For finding the maximum subarray having only 0’s, take two pointers at the start of the array, keep one of them, say it_1 fixed at index 0 while iterating the other one, say it_2, and changing the 1’s and 2’s to 0 until the constraints of changes are not violated.
Also, note when looking for maximum subarray having only 0’s there’s no need to change 0’s to something else.
Now, store the length of the subarray [ it_1, it_2] as the current maximum length,CML .We will now move it_1 forward till we can again move it_2 without violating the constraints. We will repeat these steps and keep updating CML and the final value of the CML will be the answer for maximum subarray having only 0’s.
The same will be done for the maximum subarray having only 1’s and 2’s and the overall maximum value among corresponding final CML’s will be the answer to the problem.
SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin >> t;
while (t--)
{
int start = 0;
int m = 0;
int zz = 0, xx = 0, yy = 0;
int z, x, y;
int i = 0;
string a;
int n;
cin >> n;
cin >> a;
cin >> x >> y >> z;
//for 1
while (start < n)
{
while (i < n && xx <= x && zz <= z)
{
if (a[i] == '0')
{
xx++;
}
else if (a[i] == '2')
{
zz++;
}
i++;
}
if (i < n || (i >= n && zz > z || xx > x))
{
m = max(m, i - 2 - start + 1);
}
else
{
m = max(m, n - 1 - start + 1);
}
if (start >= 0 && a[start] == '0')
{
xx--;
}
else if (start >= 0 && a[start] == '2')
{
zz--;
}
start++;
}
zz = 0, xx = 0, yy = 0;
//for 2
i = 0;
start = 0;
while (start < n)
{
while (i < n && xx <= x && yy <= y)
{
if (a[i] == '0')
{
xx++;
}
else if (a[i] == '1')
{
yy++;
}
i++;
}
if (i < n || (i >= n && xx > x || yy > y))
{
m = max(m, i - 2 - start + 1);
}
else
{
m = max(m, n - 1 - start + 1);
}
if (start >= 0 && a[start] == '0')
{
xx--;
}
else if (start >= 0 && a[start] == '1')
{
yy--;
}
start++;
}
zz = 0, xx = 0, yy = 0;
//for 0
i = 0;
start = 0;
while (start < n)
{
while (i < n && zz <= z && yy <= y)
{
if (a[i] == '2')
{
zz++;
}
else if (a[i] == '1')
{
yy++;
}
i++;
}
if (i < n || (i >= n && zz > z || yy > y))
{
m = max(m, i - 2 - start + 1);
}
else
{
m = max(m, n - 1 - start + 1);
}
if (start >= 0 && a[start] == '2')
{
zz--;
}
else if (start >= 0 && a[start] == '1')
{
yy--;
}
start++;
}
cout << m << endl;
}
return 0;
}