Can you explain what we are doing in this problem?

#1

i just saw the editorial and i can’t understand what was happening in the code

#2

Hey @mb129162 according to the problem -
Sanket has a string consisting of only a and b as the characters. Sanket describes perfectness of a string as the maximum length substring of equal characters. Sanket is given a number K which denotes the maximum number of characters he can change. Find the maximum perfectness he can generate by swapping no more than k characters.

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.

I hope the problem is clear now.

#3

if your doubt is cleared don’t forget to mark it resolved in my doubts section @mb129162 :smiley:

#4

i’m asking how the code of editorial will work?

#5

Hey @mb129162 , if you are not understanding the approach its -
this problem can be solved with help of two pointers. Let the first pointer is l and the second pointer is r. Then for every position l we will move right end r until on the substring slsl + 1… sr it is possible to make no more than k swaps to make this substring beautiful. Then we need to update the answer with length of this substring and move l to the right.

#6

here for reference https://ide.codingblocks.com/s/232024

#7

@mb129162 if your doubt is cleared please mark it as resolved

#8

I saw the editorial , why we are moving only upto < size-1 not to <size ?

#9

@mb129162 can you send the editorial. also size - 1 maybe because in his approach maybe he cant swap last element with hi foeward ones as its the last

#10
#11

@mb129162 size-1 becuase otherwise j would become sometimes s.size() while last index in s is s.size()-1 as indexing is 0th based.

#12

But it is using <size-1…it simply measn we are making a loop from 0 index to last 2nd element? Why is it so?

#13

hey its difficult to explain the logic here you can dry run the code it will come to you automatically.

#14

also as i told your earlier by < size-1 we are going till second last so j ka atmkst go to size-1 which is the last index otherwise it would go to size which is outside the string @mb129162

#15

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.