Sanket and strings problem

#1

hi, this has been a tricky problem, but i could finally get my code to work for all my sample inputs.
its still giving me trouble with the testcases for some reason, please help resolve.

Thanks!

#2

It is a really simple problem.

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.

the dry run of the above code is in the link sanket and strings

#3

Hi Aman!

Thank you for your prompt response. I cannot seem to find the link you have referenced in your concluding statement. Although i do not require the link at all.
You might’ve misunderstood my query, allow me to clarify, I actually do understand the question and how the output is calculated.
My problem is that i devised my approach and solved the question (correctly, as per the few basic strings i could test). However I have clearly missed something, since despite proper compilation and testing, my code isn’t passing your testcases.
I am new to competitive coding and am learning so much through your very helpful course, Can you assist me with this err on my approach to the problem? please refer my code (as linked) and let me know.
Thanks :slight_smile:
~Kritika

#4

Yes Kritika I see that your approach is nearly correct. But you need to take care of the cases properly.
While count > k traverse the string
again until count becomes less than k
and decrease the count when characters
are not same.

   while (r < n) { 
    if (A[r] != ch) 
        ++cnt; 

    while (cnt > k) { 
        if (A[l] != ch) 
            --cnt; 
        ++l; 
    } 

    maxlen = max(maxlen, r - l + 1); 
    ++r; 
}
#5

Do this operation for both a and b . And find the largest possible value. Full code can be found here. https://ide.codingblocks.com/s/289669

1 Like
#6

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.