Please see what is wrong in the code, it is not passing some of the testcases :- https://ide.codingblocks.com/s/406014
SanketAndStrings Question
Hey @Sakshi2004 the approach you are following is not ideally correct. It will only clear you given test case. Check for this test case:
1
abbaa
Expected output for this is: 2
Yours is giving is: 4
Think of a new approach . If it didnβt come in your mind. Let me know. Iβll help you with it.
The expected output should be 3 i guess ? ans please provide a hint for the question unable to think of it.
See this detailed description will clear your doubt
Implement the following approach:
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.
Letβs understand this with an example:
Example:
1
abba
Output:
3
Explanation:
l=0: variable to mark the left index and initialized to 0
r=0: variable to mark the right index and initialized to 0
m=0: to store the perfectness and initialised to zero
t=k: to keep track of the number of replacements we can perform at any instance of time.
- First, we will check for the string of character βaβ:
character at a[r] is βaβ, increment r
r:1
the character at a[r] is not βaβ and t>0, increment r and decrement t as we can replace one βbβ to βaβ
t:0 r:2
the character at a[r] is not βaβ and t==0. So, we cannot replace. Thus replace m by max. of m and r-l.
Repeat, while t==0:
A. if a[l]!=βaβ: increment t (because we must have done one replacement for this before and now as we are not considering this character so we can use this replacement somewhere else.)
B. increment l for each iteration of the loop.
m:2 t:0 l:1 t:1 l:2
the character at a[r] is not βaβ and t>0, increment r and decrement t as we can replace one βbβ to βaβ
t:0 r:3
character at a[r] is βaβ, increment r
r:4
replace m by max. of m and r-l.
m:2
l=0: variable to mark the left index and initialized to 0
r=0: variable to mark the right index and initialized to 0
m=0: to store the perfectness and initialised to zero
t=k: to keep track of the number of replacements we can perform at any instance of time.
- Now, we will check for the string of character βbβ:
the character at a[r] is not βbβ and t>0, increment r and decrement t as we can replace one βaβ to βbβ
t:0 r:1
character at a[r] is βbβ, increment r
r:2
character at a[r] is βbβ, increment r
r:3
the character at a[r] is not βbβ and t==0. So, we cannot replace. Thus replace m by max. of m and r-l.
Repeat, while t==0:
A. if a[l]!=βbβ: increment t (because we must have done one replacement for this before and now as we are not considering this character so we can use this replacement somewhere else.)
B. increment l for each iteration of the loop.
m:3 t:1 l:1
the character at a[r] is not βbβ and t>0, increment r and decrement t as we can replace one βaβ to βbβ
t:0 r:4
replace m by max. of m and r-l.
m:3
Hence, the output is m:
3
Also attaching code for same algorithm to get an idea.
Try for test case
1
abbaa
Also ,
strings are in form of a & b only. no need to make them lowercase.
If you want dry run for for above code, i can also provide you with that
But first understand the problem and dry run yourself to get proper implementation.
Suppose the input is
1
abbaa
So the expected output should be 3 (if we change the βbβ at position 2)
But the code you provided, gives 2 as the output
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.