Explanation of output

#1

I want to know the explanation of example given or one more test case.I am unable to understand with the given input and output.

#2

Hello @Divyansh_2000,

  1. In this problem you are given a string that is composed of only two characters ‘a’ and ‘b’.
    Example:
    abaababab

  2. Now, you are required to print the length of the substring containing all character as same(either all ‘a’ or all ‘b’):
    2 (for aa in the above-mentioned example)

  3. But, there is a twist. You are given a number k, that specifies the maximum number of changes you can make is the input string.
    Changes: replacing ‘a’ with ‘b’ or vice-a-versa.
    …Suppose, k=1 (you can make at max 1 replace)
    Then, replacing ‘b’ at 2nd position with ‘a’ will modify the string as:
    aaaababab
    So, output:
    4 (for aaaa)
    …if k=2 (you can make at max 2 replaces)
    Then, replacing ‘b’ at 2nd position and 5th position with ‘a’ will modify the string as:
    aaaaaabab
    So, output:
    6 (for aaaa)

The number you have to print is referred to as perfectness in the question.

Approach:
You can implement the following approach:
Perform following for both the characters a and b individually,

  1. Take two-pointer l and r to mark the left and right index of the string under consideration.
  2. starting from l=0,r=0,max=0,count=0.
  3. repeat until r <n (n is length of 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 element at lth index is different.
    …3.2.1. increment l.
    3.3. Compare max with count for maximum value.
    3.4. increment r.

NOTE: you can also relate this problem with the problem of Fibonacci sequence. Think.

Hope, this would help.
Give a like, if you are satisfied.

1 Like
#3

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.