i could not understand approach of this problem.can u explain me it ?l
Sanket and strings
Hey @lovely 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’.
can u give me the code of this approach?
#include <iostream>
#include <cstring>
using namespace std;
//Function to count the length of window which can be made of char ch with <= k swaps
int countMaxWindowSize(const string &s, char ch, int k)
{
int i = 0; //Left pointer
int j = 0; //Right pointer
//First move the right pointer forward by k steps.
//If the character is already ch , do not count a swap and move freely
int c = 0; //Variable to count the swaps so far
int ans = 0; //Variable to store the final answer
for (j; c < k && j < s.size() - 1; j++)
{
if (s[j] != ch)
{
//If s[j] is not ch then count it as a swap and move forward
c++;
}
if (c == k)
{
//If no of swaps has reached k, stop moving j any more forward
break;
}
}
while (i < j)
{
//Move j ahead if next element is ch as it doesn't count as a swap
while (j < s.size() - 1 && s[j + 1] == ch)
{
j++;
}
//Store the maximum length of all windows
int currentLength = j - i + 1;
ans = max(ans, currentLength);
//Move left pointer by one to slide the window
i++;
//If the char at previous position of left pointer was not ch, then that position must
//have counted as a swap earlier. Now we have a free swap available.
//Iterate right pointer forward to use that one free swap
if (j < s.size() - 1 && s[i - 1] != ch)
{
j++;
}
}
return ans;
}
int main()
{
int k;
cin >> k;
string s;
cin >> s;
if (k >= s.size())
{
//If k is larger than s.size() then we can swap all the elements to either A or B
//and obtain the answer equal to length of string
cout << s.size();
return 0;
}
//First let us check for longest perfect string of A's then we will find the same for B's and compare
int ansForA = countMaxWindowSize(s, 'a', k);
//Now we do the same for B's
int ansForB = countMaxWindowSize(s, 'b', k);
//Final answer is max of the two answers obtained above
cout << max(ansForA, ansForB);
return 0;
}
i could not understand the following lines in code .can you explain what is mean by free swap available?
//If the char at previous position of left pointer was not ch, then that position must
//have counted as a swap earlier. Now we have a free swap available.
//Iterate right pointer forward to use that one free swap
if (j < s.size() - 1 && s[i - 1] != ch)
{
j++;
}
}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
is the question approach only tricky to me or u initially found it hard 
It’s initially thought, give some time to it. You’ll understand it for sure.
1 Like
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.