I have done this problem. Using sliding window technique is there any other way to do it…
Sanket and string
@shampblocks
hello shubham ,
sliding window is most optimised approach.
another approach can be a binary search.
you can apply binary search on maximum length
1 Like
how to solve with binary search can you ellaborare??
@shampblocks
property - if there is no perfect substring of length L in given string then obviously there wont be any perfect substring of size L+1 ,L+2 so on…
because of this property we can use binary search on length. we will first check if there exist any perfect substring of length n/2 or not . if exist then search for bigger length {n/2 , n} else search in {1 , n/2 }. standard binary search problem
But in this question we just not to find the perfect substring we have to use k maximum swap to make it perfect…
let say k=2 and L = 6 (aabbaa) count of a in considered substring is 4 and count of b=2 we can convert 2 b to a to make it perfect…
u need to write a function that will check whether considererd substring is perfect or can be turned into perfect
But why we changing one a we can change 2 b to make it perfect of maximum length 6…
So how should we proceed using binary search I still not got the correct way how to start with binary search…
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.
This link. Is not working…
Feedback link you provided… That is not working…
I liked that binary search approach I get that approach after doing problem of aggressive cow and want to give positive feedback that’s why asking about feedback link but ya thanks for that approach…
1 Like