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.

  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

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