Sankt and strings problem

#1

Please give me just a hint on how to approach this problem

#2

Hello @dsingh200021,

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 untill 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.

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

1 Like
#3

There are few issues with your code:

  1. It is mentioned in the code, 2 ≤ N ≤ 10^5.
    And you have declared a character array of size 100 only.
    It’s fine to work with char array. But why don’t you rather use string.
    As, it’s easier to find it’s length.
    You have many functions associated with strings which makes modification easier.

  2. As you are not including ‘\0’ while calculating length.
    So, for loop should iterate until i<n.

  3. you should check for a[l]:
    if(a[l]!=a[i]) count++; // because you will replace only if any element is different from the very first element i.e. a[l] of the concerned string.

  4. The following code is an incorrect logic for what you are trying to do:
    if(count>k){
    l=0; //because of this line
    while(count>k){
    if(a[l]!=a[l+1])
    count–;
    l++;
    }

if you want you can refer to this page for better understanding.

Feel free to ask if you have doubts.
Hope, this will help.

1 Like
#4

I have modified your code.

You can check it here:

I would suggest you to dry run this code for any of the test case to better understand it’s flow.
I have also written many comments for the better understanding.

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

1 Like
#5

Thanks I understood it
BUT your code is NOT PASSING TESTCASE 1,it has passed testcase 2.
I tried a lot to find problem I am not able to find any problem.
Kindly check it as it is not passing the first testcase

#6

This is happening because of the following check.

        if(count==k){
            maxlen = max(maxlen, r - l + 1); 
        }

It will fail for the case when k has a large value.
Example:
5
ababa
I will never perform any 5 changes. The maximum changes would be 3, i.e a to b.
Then, our program will never update value of maxlen.

Solution:
Remove this condition and execute the maxlen logic before r++;

1 Like
#7

Give a like, if you are satisfied.
Mark this doubt as resolved if you have no more doubts regarding this problem.

1 Like