how to approach this question ???
Sanket and string
hello @amishakumari
Basically, there is a string which consists of only a and b. A substring is a contiguous sequence of characters within a string. Our aim is to generate substrings of a and b by swapping characters such that the lengths of substrings of either a or b is maximum possible. The only constraint we have here is that only k swaps are allowed. So, you have to tell the maximum possible length of the substrings that can be generated. By swapping, we mean that a can be replaced by b and b can be replaced by a.
For example:
Consider the following string: abba and k = 2
So, we can make only two swaps
abba (swaps = 0)
aaba (swaps = 1)
aaaa (swaps = 2)
Thus, the maximum length of substring is 4.
Consider the string: ababab and k=2
ababab (swaps = 0)
aaabab (swaps =1)
aaaaab (swaps = 2)
Thus, the maximum length of substring is 5.
You can look for the following Approach: ( TWO POINTERS)
Perform following for both the characters a and b individually,
Take two pointers l and r to mark the left and right index of the string under consideration.
starting from l=0,r=0,max=0,count=0.
repeat until r <n(length of the string)
3.1. increase the count whenever you find a different character(by different we mean if we are forming a string of a only, then b is different).
3.2. while count is greater than k,
3.2.1. decrement the count by one if the element at lth index is different.
3.2.1. increment l.
3.3. Compare max with count for maximum value.
3.4. increment r.
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.