3

Check if a string can be made empty by repeatedly removing given subsequence

 1 year ago
source link: https://www.geeksforgeeks.org/check-if-a-string-can-be-made-empty-by-repeatedly-removing-given-subsequence/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

Check if a string can be made empty by repeatedly removing given subsequence

  • Last Updated : 03 Aug, 2021

Given a string str containing characters ‘G’ and ‘F’ only, the task is to check if the given string str can be made empty after removing all subsequences of the form “GFG”.

Examples:

Input : N = 6, str[] = “GFGFGG”
Output : Yes
Explanation : Two strings of “GFG” can be made with the first one with indices {0, 1, 5} and the second one with the remaining indices.

Input : N = 10, str = “GGFFGFGFFG”
Output : No
Explanation : It is not possible, because even after making all possible strings one F will remain.

Approach: It can be seen that in order to make GFG, 2 G and one F in the middle are needed, so if the count of the G is not equal to twice the count of F, it is never possible to make some number of GFG complete from the given string. Another thing to check is that the number of G in the latter thing must never be less than the number of F as the string is GGGFFGFGFFG, so it can be seen that the last two, FF have only one G, so it will not be possible to make GFG from both of them so our answer will again be No. And the last condition to check is that the count of G passed is never less than the count of F in order to make GFG. Follow the steps below to solve the problem:

  • Initialize the variables countG and countF as 0 to store the count of G and F in the string str[].
  • Iterate over the range [0, N] using the variable i and perform the following steps:
    • If str[i] is equal to G, then, increase the value of countG by 1, else, increase the value of countF by 1.
  • If 2*countF is not equal to countG, then, it’s not possible so print “NO” and return.
  • Initialize the variables id as 0 to calculate the count of G and F till a particular index and variable flag as true to store the answer.
  • Iterate over the range [0, N] using the variable i and perform the following steps:
    • If str[i] is equal to ‘1’, then decrease the value of countG by 1 and increase the value of id by 1.
    • Else, decrease the value of countF by 1 and decrease the value of id by 1.
    • If id is less than 0, then extra G will be in the end and won’t be utilized so set the value of flag to false and break.
    • If countG is less than countF, then extra F will be in the end and won’t be utilized so set the value of flag to false and break.
  • If flag is equal to true, then, print “YES”, else print “NO”.

Below is the implementation of the above approach.

  • Python3
  • Javascript
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to check if a string can be
// made empty by removing all
// subsequences of the form "GFG" or not
void findIfPossible(int N, string str)
{
int countG = 0, countF = 0;
for (int i = 0; i < N; i++) {
if (str[i] == 'G')
countG++;
else
countF++;
}
if (2 * countF != countG) {
cout << "NO\n";
}
else {
int id = 0;
bool flag = true;
for (int i = 0; i < N; i++) {
if (str[i] == 'G') {
countG--;
id++;
}
else {
countF--;
id--;
}
if (id < 0) {
flag = false;
break;
}
if (countG < countF) {
flag = false;
break;
}
}
if (flag) {
cout << "YES\n";
}
else {
cout << "NO\n";
}
}
}
// Driver Code
int main()
{
int n = 6;
string str = "GFGFGG";
findIfPossible(n, str);
return 0;
}
Output: 
YES

Time Complexity: O(N)
Auxiliary Space: O(1)


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK