Why wrong answer in some test cases
Check for this test case:
3
aaabbabbbab
Expected output is: 9
Yours is giving this: 7
I guess this will let you know your mistake.
I guess the approach you are using is not ideal one, follow this detailed explanation
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 the same algorithm
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.