The logic is same as author’s solution where instead of maintaining the prefix sums in an array, we calculate them on the fly using sliding window concept.
The complexity is O(n^2) as you are building the whole sub-string again (StringBuilder function is called n times).
Okay Thanks, i had read somewhere that appending as well as deleting from 0th index would only take o(1). Can you point you whats wrong with the algo as it gave WA in the contest? or any edge cases i’m not considering.
Can someone, explain the intuition behind the approach in the editorial for sub-case #2. I understand the code and process, but how do you come up with such a solution (For example, to decide to go column-wise instead of row-wise and calculate prefix sum etc.).
Hey Gyanendra!
I thought of the same approach but fail to understand why my solution is not working. Could you please help me out?
Link to my solution: CodeChef: Practical coding for everyone
Thanks in advance…
my solution in O(n) time complexity & O(1) space complexity.
#include <bits/stdc++.h>
#include
#include
#define wh while(t–)
#define fl(i,a,n) for(i=a;i<n;i++)
#define speed ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
typedef long long ll;
int main() {
speed
ll i,j,n,t,k,u,l,v,u1,v1,q;
cin >> t;
string s;
wh
{
cin >> n >> k;
cin >> s;
l=u=v=0;
fl(i,1,n)
{
if(s[i]!=s[i-1])
l++;
if(i<=k-1)
v+=l;
if(i>=n-k)
{
u+=l;
}
}
u=u-v;
cout << u << “\n”;
}
return 0;
}