Kartik Bhaiya has a string consisting of only βaβ and βbβ as the characters. Kartik Bhaiya describes perfectness of a string as the maximum length substring of equal characters. Kartik Bhaiya is given a number k which denotes the maximum number of characters he can change. Find the maximum perfectness he can generate by changing no more than k characters.
please provide me the answer to this problem along with comments so that i can understand it easily
SanketAndStrings
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β.
see this:
if this solves your doubt please mark it as resolved