Home » Technical Interview Questions » String Interview Questions » Remove ‘b’ and ‘ac’ from a given string

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

## 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;
}```

### 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

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;
}```