Answer not passing

#1

sol: https://ide.codingblocks.com/s/388875

prob: https://hack.codingblocks.com/app/contests/1975/446/problem

logic: find the element which occurs more and have done some calculations related to it.

#2

Hey @raghav007 i have seen your code in it, you are using sort function that to N times thus resulting your time complexity in N*O(NlogN) whereas you have to do this in O(N) time complexity. Try to optomize your code, and if you want any help in the implementation, then do let me know i will tell you the ideal implementation.

#3


I have done using frequency array this time the answer seems correct but still not passing

#4

I guess the approach you are using is not ideal one, follow this detailed explanation and understand it with your utmost presence
See this detailed description will clear your doubt
Implement the following approach:
Perform following for both the characters a and b individually,

  1. Take two pointers 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(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.

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

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

#5

how are we going to get out of this while loop because t is not getting decremented

#6

You don’t have to use while loop for t , just iterate on indexes of string and you will get the intuition. Try to dry run the code i have given with different formats. If it will not be helpful then i will give you the dry run also to understand it better.

#7

in the code t or k is not being decremented

#8

See this one, had attached wrong code


In this code there’s comment too. Will be easy for you to understand.

#9

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.