Remove ‘b’ and ‘ac’ from a given string


StringViews 2875

Given a string, write a function to eliminate all “b” and “ac” in the string

NOTE : we should traverse the string only once and no extra space is allowed

Method 1

In this method we will remove ‘ac’ only if ‘a’ and ‘c’ are consecutive

Example

INPUT :
s = “abcabc”

OUTPUT :
“acac”

In this  method the main idea is to use two state machine, If the previous character to the current character is ‘a’, then the state is TWO otherwise state is ONE

Algorithm

Traverse through the given string with variable i and add characters except ‘b’ and ‘ac’ using variable j .

1. If state is ONE, and the current character is ‘a’ or ‘b’ then do not copy the current character to the output string as we need to remove ‘b’ and the next character cannot be ‘c’.

2. If state is TWO and current character is not ‘c’, then add the previous character(ie, nothing but ‘a’) . Then we check the current character, if current character is not ‘b’ and not ‘a’, then we copy it to output string.

ie, Implementation for string s = “abc”,

step1 : i = 0(‘a’), state = ONE, j = 0
Just change the state to TWO

step2 : i = 1(‘b’), state = TWO, j= 0
Add the previous character ie, s[j] = ‘a’, increment j to 1
Current char is ‘b’, so dont add it and change state to ONE

step3 : i = 2(‘c’), state = ONE, j = 1
Just add the current character ie, s[j] = s[i]
Print s[]

C++ Program

#include <iostream>
using namespace std;
#define ONE 1
#define TWO 2
 
// The main function that removes occurences of "a" and "bc"
// in input string
void removeBAndAC(char *s)
{
    //Starting the state will be ONE
    int state = ONE;
 
    //variable for storing chars in output string
    int j = 0;
 
    for (int i = 0; s[i] != '\0'; i++)
    {
        //state is ONE and char is neither a or b, then copy char to output
        if (state == ONE && s[i] != 'a' && s[i] != 'b')
        {
            s[j] = s[i];
            j++;
        }
        //state is TWO and char in not c
        if (state == TWO && s[i] != 'c')
        {
            s[j] = 'a';
            j++;
            //state is TWO and char is neither a or b, then copy char to output    
            if (s[i] != 'a' && s[i] != 'b')
            {
                s[j] = s[i];
                j++;
            }
        }
 
        // Change state according to current character
        state = (s[i] == 'a')? TWO: ONE;
    }
 
    // If last character was 'a', copy it to output
    if (state == TWO)
    {
        s[j] = 'a';
        j++;
    }
 
    // Set the string terminator
    s[j] = '\0';
}
 

int main()
{
    char s1[] = "abcabc";
    removeBAndAC(s1);
    cout << s1 << endl;
 
    char s2[] = "acbac";
    removeBAndAC(s2);
    cout << s2 << endl;
 
    return 0;
}

Try It

Method 2

This method is same as Method 1 but, here the output will not contain ‘b’ and ‘ac’. ie, after removing b and ac in below example, string  becomes “acac”, this string contains ac, so remove ac’s

Example

INPUT :
s = “abcabc”

OUTPUT :
” ”

Algorithm

The algorithm is same as Method 1, but below condition is added

1. If there is an ‘ac’ in the output string remove it

ie, if (j >1 && str[j-2] == ‘a’ && str[j-1] == ‘c’)
j = j – 2;

Implementation for string s = “abc”,

step1 : i = 0(‘a’), state = ONE, j = 0
Just change the state to TWO

step2 : i = 1(‘b’), state = TWO, j= 0
Add the previous character ie, s[j] = ‘a’, increment j to 1
Current char is ‘b’, so dont add it and change state to ONE

step3 : i = 2(‘c’), state = ONE, j = 1
Just add the current character ie, s[j] = s[i], increament j to 2
Now, s[j-2] == ‘a’ and s[j-1] = ‘c’, so make j = j-2

Print s[]

C++ Program

#include <iostream>
using namespace std;
#define ONE 1
#define TWO 2
 
// The main function that removes occurences of "a" and "bc"
// in input string
void removeBAndAC(char *s)
{
    //Starting the state will be ONE
    int state = ONE;
 
    //variable for storing chars in output string
    int j = 0;
 
    for (int i = 0; s[i] != '\0'; i++)
    {
        //state is ONE and char is neither a or b, then copy char to output
        if (state == ONE && s[i] != 'a' && s[i] != 'b')
        {
            s[j] = s[i];
            j++;
        }
        //state is TWO and char in not c
        if (state == TWO && s[i] != 'c')
        {
            s[j] = 'a';
            j++;
            //state is TWO and char is neither a or b, then copy char to output    
            if (s[i] != 'a' && s[i] != 'b')
            {
                s[j] = s[i];
                j++;
            }
        }
        if(s[j-2] == 'a' && s[j-1] == 'c')
        {
            j = j-2;
        }
 
        // Change state according to current character
        state = (s[i] == 'a')? TWO: ONE;
    }
 
    // If last character was 'a', copy it to output
    if (state == TWO)
    {
        s[j] = 'a';
        j++;
    }
 
    // Set the string terminator
    s[j] = '\0';
}
 

int main()
{
    char s1[] = "abcabc";
    removeBAndAC(s1);
    cout << s1 << endl;
 
    char s2[] = "aacaaa";
    removeBAndAC(s2);
    cout << s2 << endl;
 
    return 0;
}

Try It

 

Translate »