# Remove “b” and “ac” from a given string

I coded this solution for this problem:

Given a string, eliminate all “b” and “ac” in the string, you have to replace them in-place, and you are only allowed to iterate over the string once

Seems to work but I am not sure if I violated the "you are only allowed to iterate over the string once" requirement. Did I? Other feedback also welcome.

using System.IO;
using System;
using System.Text;
class Program
{
static void Main()
{
StringBuilder test  = new StringBuilder("ababac");

try
{

int i=0;
while( i<test.Length )
{
if(test[i] == 'b')
{
if(i!=test.Length-1){
test[i] = test[i+1];
test.Remove(i+1,1);
}
else
test.Remove(i,1);

}else if(i<test.Length -1 && test[i] == 'a' && test[i+1]=='c')
{

if(i!=test.Length-2)
{
test[i] = test[i+2];
test[i+1] = test[i+3];
test.Remove(i+2,1);
test.Remove(i+2,1);
}
else
{
test.Remove(i,1);
test.Remove(i,1);
}
}
else
{
i++;
}
}

}catch(Exception ex)
{
Console.WriteLine(ex.ToString());

}
Console.WriteLine(test.ToString());
}
}


Sample

In:

acbac
aababc

Output:

aaac

• "You have to replace them in place". I would argue that dumping it into a StringBuilder and removing characters is functionally equivalent to converting the string to a linked list and removing character nodes, which is NOT in-place. If you are going to do that, it would be cleaner to only copy the valid characters to a new StringBuilder and return it. – Zack Apr 24 '16 at 20:39
• @Zack I had thought that due to using remove I am violating the requirement to iterate only once. – user103738 Apr 24 '16 at 20:43
• For the requirement "iterate only once", what you are doing is pretty standard. It really just means that you get one "pass" over the indexes. Look ahead/behind is fine. You are meeting the spirit of that part of the requirement. – Zack Apr 24 '16 at 20:47
• @Zack Hm I thought using remove I violated iterate only once requirement, not the one you mention. – user103738 Apr 24 '16 at 20:49
• I would argue that "remove" is fine. As to my original "in-place" comment, after thinking on it some more it seems to me that the requirement was really designed with c/c++ in mind where strings are really just arrays of characters. Modern languages, including C#, handle string differently enough that an "in-place" requirement makes little sense and is not practical to try to enforce. – Zack Apr 24 '16 at 21:00

First, realize that in .NET, strings are immutable--it's impossible to actually modify a string "in-place" as asked here. You can do some things that look like modifying a string in place, such as using += on a string--but what that really does is create an entirely new string with the new contents, then modifies the reference to refer to the new contents.

That said, the request is probably pointed toward basically ignoring how things happen under the hood, and writing the code as-if you were able to modify the string. I'd guess the idea they had in mind was to have code that keeps track of two locations (e.g., indices) in the string: a source and a destination.

These initially start out equal (at the beginning of the string). You then walk through the string copying one character at a time from the source location to the destination location (or if the two locations are equal, just advance both without changing anything else). If you get to a character (or group of characters) you're supposed to delete, you just advance the source location without advancing the destination.

• Source and destination point to same memory location? (If you show small sample of what you mean will be easier to follow) – user103738 Apr 24 '16 at 21:52
• @user200300: They both start out pointing to the same location (the beginning of the string). When you find something you want to delete, however, you advance the source without advancing the destination, so they no longer point to the same place. – Jerry Coffin Apr 24 '16 at 21:54

Letting the delete part aside...

I believe you could do better with the iterate over the string once part. Everytime you find an a you look one char ahead, and then again when it is its turn. You could avoid this by iterating over the string one char at the time and set a flag to true whenever you find an a and in the next iteration remove both if c and in any case set flag to false.

Your way of removing characters from the string seems a bit obfuscated to me.

Wouldn't the following code work...?

    for(int i = 0; i < test.Length;)
{
if(test[i] == 'b')
{
test.Remove(i,1);
}
else if(test[i] == 'a' && i+1 < test.Length && test[i+1] == 'c')
{
test.Remove(i,2);
}
else
{
i++;
}
}

• Think about i == test.Length-1 and 'a'==test[i]. – greybeard Apr 25 '16 at 12:56
• @greybeard Well, if i == test.Length-1 and 'a'==test[i] then the middle subexpression i+1 < test.Length will return false and the third subexpression (comparision to 'c') won't be evaluated. The whole condition returns false and the control is passed to else { i++; } which causes the loop termination on the next i < test.Length check. Do I miss something? – CiaPan Apr 25 '16 at 13:05
• No, I missed the "middle condition/subexpression", the only excuse being I'd never code it like that ;-/ – greybeard Apr 25 '16 at 13:11
• I considered the test[i] a common subexpression of both conditions, so I've put it in front so it could be fetched once, then cached by a compiler in an unnamed temporary variable (possibly a fast CPU register). One could also do it explicitly with some char c = test[i]; if( c == ...) or even with switch(test[i]) {...} — then of course we don't need checking i+1<test.Length if the i-th character isn't 'a', so I deliberately postponed it until it is necessary, just before accessing the item at position i+1 . – CiaPan Apr 25 '16 at 13:21
• @greybeard (Forgot to add a 'ping' in the previous comment, so I do it now.) – CiaPan Apr 25 '16 at 13:53

# Reference Implementation

Because there has been some interest in a fully compliant implementation, I have created one. This loops over each character once. There is no look ahead/behind (although I personally think that looking around fits within the spirit of the instructions) and instead I cache the 'a' character when checking for a 'c' on the next pass. This of course makes the code look a little ugly, as like fizzbuzz, the checks are not quite similar.

This was written and tested in C.

void removeTokens(char str[], size_t length)
{
int ixDst = 0;
char prevLetter = '\0';
for(int ixSrc=0; ixSrc<=length; ixSrc++)
{
if(prevLetter != '\0' &&  str[ixSrc] != 'c')
{
str[ixDst++] = prevLetter;
prevLetter = '\0';
}

switch(str[ixSrc])
{
case 'a':
prevLetter = str[ixSrc];
break;
case 'b':
break;  //no copy
case 'c':
if(prevLetter == 'a')
{
prevLetter = '\0';
break;  //no copy if prev char was a
}
//fallthrough
default:
str[ixDst++] = str[ixSrc];
break;

}
}
str[ixDst] = '\0';
}