Last Updated: 7 Mar, 2021
Equal Number Of Boys And Girls
Moderate
Asked in company
There are ‘N’ students standing in a row. Students are comprised of both girls and boys. Kevin is their teacher, who wants to pick a group of students that have an equal number of boys and girls. Kevin does not want to disturb the whole row and so, he only wants to pick students that are adjacent to each other. Formally, he can only pick a subarray, not a subsequence.
A complete row is given as an array of characters (as a string 'S'), you have to find the length of the longest such subarray which follows the above criteria.
Input Format:
The first line contains a single integer ‘T’ representing the number of test cases.
The first line of each test case will contain a single integer ‘N’ which represents the number of students in the row.
The second line of each test case contains a string ‘S’ of length ‘N’ which is comprised of two characters ‘G’ and ‘B’ where ‘B’ denotes Boy and ‘G’ denotes the Girl.
Output Format:
For each test case, print the length of the longest possible subarray that Kevin pick so that students are adjacent to each other.
Output for every test case will be printed in a separate line.
Note:
You don’t need to print anything; it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 10
1 <= N <= 10000
S[ i ] = ‘B’ or ‘G’
Where S[i] denotes the ‘i-th’ character of the given string ‘s’.
Time limit: 1 sec
Approaches
The basic idea of this approach is to loop through each subarray and find the length of the longest subarray which satisfies the property mentioned in the problem statement.
The steps are as follows:
- Create a variable to store the answer (say, “ans”) and Initialise it with 0.
- Iterate through ‘s’ (say, iterator = ‘i’)
- Iterate again through ‘s’ from ‘i’ to end of ‘s’ (say, iterator = ‘j’)
- Iterate through ‘s’ from ‘i’ to ‘j’ and check if it has an equal number of boys and girls.
- If it has, then check if it is also longest or not by comparing its length with “ans”. If true then store its length into “ans”.
- Iterate again through ‘s’ from ‘i’ to end of ‘s’ (say, iterator = ‘j’)
- Return “ans”.
The basic idea of this approach is to traverse through the string and keeps calculating the number of boys and girls and pick subarrays that satisfy the criteria and then finally, select the subarray that has the maximum length.
The steps are as follows:
- Create a variable to store the answer (say, “ans”) and Initialise it with -1.
- Iterate through ‘s’ (say, iterator = ‘i’)
- Create two variables “boys” and “girls” to store the number of boys and girls.
- Iterate again through ‘s’ from ‘i’ + 1 to end of ‘s’ (say, iterator = ‘j’)
- Check the character at ‘i’ the increment the value of its corresponding variable by 1.
- Now, check if “boys” is equal to “girls” and the length of this subarray is maximum then “ans”. If it is true then “ans” = length of current subarray.
- Return “ans”.
The basic idea of this approach is to store the count of boys and girls (relatively) and keep iterating through ‘s’ and whenever found the same count again then check of the longest subarray.
The steps are as follows.
- Create a HashMap “mp” and two variables “count” and “ans”. Where “count” is used for storing the relative count of boys and girls and “ans” is for storing the length of the longest required subarray.
- Store -1 at mp[0] so as to pick the first subarray that satisfies the conditions.
- Iterate through ‘s’. (say, iterator = ‘i’)
- If there is a boy at position ‘i’ then increment the count by 1. Otherwise, decrease the count by 1.
- If this count exists in HaspMap “mp” then store the maximum between “ans” and ( ‘i’ - mp[count] ) in “ans”.
- Otherwise, store the index ‘i’ into mp[count].
- Return “ans”.