How to collect different characters in a String
How to collect different characters in a String
you can simply input like this:
String s = sc.next();
if your are asking for the approach
You can solve this problem in O(n) time using the two pointer approach.
- Make two variabes , say i and j .
- i defines the beginning of a window and j defines its end.
- Start i from 0 and j from k.
- Letβs talk about the singular case when we are considering the max window for only 'aβs and consider only the swapping of b-> a. If we are able to get the answer for max window of consecutive 'aβs , we can simply implement the same algo for the max βbβ window as well.
- So we started i from 0 and j from k.
- Move j ahead freely as long as there are βaβ characters at s[ j ] position.
- Maintain a count variable which counts the number of swaps made or the number of 'bβs in our A window.
- If you encounter a βbβ char at s[ j ] position , increment the count variable. Count should never exceed k .
- Take the size of the window at every point using length = j - i + 1;
- Compute the max size window this way and do the same for βbβ as well.
- Output the maximum size window of βaβ and βbβ.
Why should we need to count the no. of swaps and what i have to do with the size of the window
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
hey please confirm once .this( https://hack.codingblocks.com/app/contests/720/446/problem) is the question you are referring to right?
yes question is same but the sample output is 4 not 3
sample input is 2 abba
i have shown you the working for
1
abba
please go through it once