Maximum number of removals of given subsequence from a string
Last Updated :
03 Oct, 2022
Given string str, the task is to count the maximum number of possible operations that can be performed on str. An operation consists of taking a sub-sequence ‘gks’ from the string and removing it from the string.
Examples:
Input: str = “ggkssk”
Output: 1
Explanation: After 1st operation: str = “gsk”
No further operation can be performed.
Input: str = “kgs”
Output: 0
Approach:
- Take three variables g, gk, and gks which will store the occurrence of the sub-sequences ‘g’, ‘gk’, and ‘gks’ respectively.
- Traverse the string character by character:
- If str[i] = ‘g’ then update g = g + 1.
- If str[i] = ‘k’ and g > 0 then update g = g – 1 and gk = gk + 1 as previously found ‘g’ now contributes to the sub-sequence ‘gk’ along with the current ‘k’.
- Similarly, if str[i] = ‘s’ and gk > 0 then update gk = gk – 1 and gks = gks + 1.
- Print the value of gks in the end.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>
using namespace std;
int maxOperations(string str)
{
int i, g, gk, gks;
i = g = gk = gks = 0;
for (i = 0; i < str.length(); i++) {
if (str[i] == 'g') {
g++;
}
else if (str[i] == 'k') {
if (g > 0) {
g--;
gk++;
}
}
else if (str[i] == 's') {
if (gk > 0) {
gk--;
gks++;
}
}
}
return gks;
}
int main()
{
string a = "ggkssk";
cout << maxOperations(a);
return 0;
}
|
Java
class GFG
{
static int maxOperations(String str)
{
int i, g, gk, gks;
i = g = gk = gks = 0;
for (i = 0; i < str.length(); i++)
{
if (str.charAt(i) == 'g')
{
g++;
}
else if (str.charAt(i) == 'k')
{
if (g > 0) {
g--;
gk++;
}
}
else if (str.charAt(i) == 's')
{
if (gk > 0)
{
gk--;
gks++;
}
}
}
return gks;
}
public static void main(String args[])
{
String a = "ggkssk";
System.out.print(maxOperations(a));
}
}
|
Python 3
def maxOperations( str):
i, g, gk, gks = 0, 0, 0, 0
for i in range(len(str)) :
if (str[i] == 'g') :
g += 1
elif (str[i] == 'k') :
if (g > 0) :
g -= 1
gk += 1
elif (str[i] == 's') :
if (gk > 0) :
gk -= 1
gks += 1
return gks
if __name__ == "__main__":
a = "ggkssk"
print(maxOperations(a))
|
C#
using System ;
public class GFG{
static int maxOperations(string str)
{
int i, g, gk, gks;
i = g = gk = gks = 0;
for (i = 0; i < str.Length; i++) {
if (str[i] == 'g') {
g++;
}
else if (str[i] == 'k') {
if (g > 0) {
g--;
gk++;
}
}
else if (str[i] == 's') {
if (gk > 0) {
gk--;
gks++;
}
}
}
return gks;
}
public static void Main()
{
string a = "ggkssk";
Console.WriteLine(maxOperations(a)) ;
}
}
|
PHP
<?php
function maxOperations($str)
{
$i = $g = $gk = $gks = 0;
for ($i = 0; $i < strlen($str); $i++)
{
if ($str[$i] == 'g')
{
$g++;
}
else if ($str[$i] == 'k')
{
if ($g > 0)
{
$g--;
$gk++;
}
}
else if ($str[$i] == 's')
{
if ($gk > 0)
{
$gk--;
$gks++;
}
}
}
return $gks;
}
$a = "ggkssk";
echo maxOperations($a);
?>
|
Javascript
<script>
function maxOperations(str)
{
let i, g, gk, gks;
i = g = gk = gks = 0;
for (i = 0; i < str.length; i++)
{
if (str[i] == 'g')
{
g++;
}
else if (str[i] == 'k')
{
if (g > 0) {
g--;
gk++;
}
}
else if (str[i] == 's')
{
if (gk > 0)
{
gk--;
gks++;
}
}
}
return gks;
}
let a = "ggkssk";
document.write(maxOperations(a));
</script>
|
Time Complexity: O(n)
Auxiliary Space: O(1)
Like Article
Suggest improvement
Share your thoughts in the comments
Please Login to comment...