TINDER - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice

Contest Code Battle 2021.1.2

Author: Utkarsh Goel, Aditya Rana

Tester: Utkarsh Goel

Editorialist: Raghav Vashishth

DIFFICULTY:

Cakewalk

PREREQUISITES:

Basic observations, Greedy Algorithm

PROBLEM:

We are given a string showing a list of males and females shown using only two characters M and F respectively with length N. We want to divide the string into as small substrings as possible keeping the number of both characters equal in every substring. Also, they must keep the substring contiguous. So they can not pick characters from random places in the string and put them together, instead, they should create divisions in the string. Note that each character should be part of at-least 1 and only 1 substring. We have to find out what is the maximum number of such groups formed. It is guaranteed that one such grouping will always exist.

QUICK EXPLANATION:

If minimum length contiguous substring having number of males and females equal are chosen then the no. of groups will be maximised.

EXPLANATION:

  1. We maintain the count of number of groups named and the difference between the count of males and females.
  2. Using loop we transverse the String and increase the difference when M is encountered and decrease it when F is encountered.
  3. At each point check if the difference is 0 , If yes then increase group count as that is the minimum contiguous substring which has the number of male and female equal.
  4. At the end of loop we will have the maximum number of groups possible.

TIME COMPLEXITY:

O(N) per test case where N is the length of the String.

SOLUTIONS:

Language: C++, Python

Setter's Solution 
#include <bits/stdc++.h>
using namespace std;
int main()
{
  long long t;
  cin >> t;
  while (t--)
  {
   int n;
   cin >> n;
   string s;
   cin >> s;
   long long ans = 0;
   long long r = 0;
   for (long long i = 0; i < s.length(); i++)
   {
     if (s[i] == 'F') r--;
     else r++;
     if (r == 0) ans++;
   }
  cout << ans << endl;
  }
 return 0;
}
Tester's Solution 
t = int(input())
while t!=0:
      n=int(input())
      s=input()
      r=0
      ans=0
      for i in range(len(s)):
             if s[i]=='F':
                     r-=1
             else:
                     r+=1
             if r==0:
                    ans+=1
       if (len(s) == n):
	         print(ans)
       t-=1;
2 Likes