can you give me some hint how to solve
SanketAndStrings
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.
sir in your code you have implemented some other logic
By mistake attached wrong code, see this
sir the previous code is also correct only space complexity is used there.Can you please explain that approach also
Itβs an intuitive approach. Just try to do dry run for different test cases. You will get the intuition. One of the dry run is done here. You can see, it will help you in understanding it better.
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.