i am not able to find the logic to solve this problem please help and give logic to how can we solve these problem. in optimal time
Sanket and string problem
Hi @amanm2292
You can solve this problem in O(n) time using the two pointer approach.
Make two variabes , say i and j .
i defines the beginning of a window and j defines its end.
Start i from 0 and j from k.
Let’s talk about the singular case when we are considering the max window for only 'a’s and consider only the swapping of b-> a. If we are able to get the answer for max window of consecutive 'a’s , we can simply implement the same algo for the max ‘b’ window as well.
So we started i from 0 and j from k.
Move j ahead freely as long as there are ‘a’ characters at s[ j ] position.
Maintain a count variable which counts the number of swaps made or the number of 'b’s in our A window.
If you encounter a ‘b’ char at s[ j ] position , increment the count variable. Count should never exceed k .
Take the size of the window at every point using length = j - i + 1;
Compute the max size window this way and do the same for ‘b’ as well.
Output the maximum size window of ‘a’ and ‘b’.
@vardaan_sharma
Please do not share codes like this . It ruins the spirit of learning . We are here to learn , not just copy paste the codes and earn points on challenges.
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.
sir , why are we starting j from k and not the just next element of i (i+1) ?
@chahatkumar
It is because we wish to make a window of size k. So our answer be atleast k for this problem . We can do that as well … Start j from i+1 , however we would simply end up with j=k only and that would be the first value that we would actually consider for our answer. So why not just start from there .