Sylvain Boisse Sylvain Boisse makes a very good observation about the importance of the guarantee that
Sylvain Boisse makes a very good observation about the importance of the guarantee that
Sylvain Boisse makes a very good observation about the importance of the guarantee that
and a good suggestion to use a stack. Observe that if we encounter a character which neither starts a potential match nor continues the current potential match then it blocks all (unremoved) characters before it from being part of a word, since they would have to span it. Therefore the stack can be clearercleared, and the code can be remarkably simple.
static string RepeatedRemoval(string initial, string removed)
{
if (removed.Length == 0) return initial;
StringBuilder sb = new StringBuilder(initial.Length);
char startRemoved = removed[0];
// The main case
int[] stack = new int[initial.Length + 1];
int stackIdx = 0;
foreach (char ch in initial)
{
sb.Append(ch);
// Since all characters in removed are distinct, a match for removed[0] starts a new match
if (ch == startRemoved) stack[++stackIdx] = 1;
// A match for the next character expected extends the current match
else if (ch == removed[stack[stackIdx]]) ++stack[stackIdx];
// And any other character blocks everything up to now from being part of a match
else stackIdx = 0;
if (stack[stackIdx] == removed.Length)
{
--stackIdx;
sb.Length -= removed.Length;
}
}
return sb.ToString();
}
and a good suggestion to use a stack. Observe that if we encounter a character which neither starts a potential match nor continues the current potential match then it blocks all (unremoved) characters before it from being part of a word, since they would have to span it. Therefore the stack can be clearer, and the code can be remarkably simple.
static string RepeatedRemoval(string initial, string removed)
{
if (removed.Length == 0) return initial;
StringBuilder sb = new StringBuilder(initial.Length);
char startRemoved = removed[0];
// The main case
int[] stack = new int[initial.Length + 1];
int stackIdx = 0;
foreach (char ch in initial)
{
sb.Append(ch);
// Since all characters in removed are distinct, a match for removed[0] starts a new match
if (ch == startRemoved) stack[++stackIdx] = 1;
// A match for the next character expected extends the current match
else if (ch == removed[stack[stackIdx]]) ++stack[stackIdx];
// And any other character blocks everything up to now from being part of a match
else stackIdx = 0;
if (stack[stackIdx] == removed.Length)
{
--stackIdx;
sb.Length -= removed.Length;
}
}
return sb.ToString();
}
and a good suggestion to use a stack. Observe that if we encounter a character which neither starts a potential match nor continues the current potential match then it blocks all (unremoved) characters before it from being part of a word, since they would have to span it. Therefore the stack can be cleared, and the code can be remarkably simple.
static string RepeatedRemoval(string initial, string removed)
{
if (removed.Length == 0) return initial;
StringBuilder sb = new StringBuilder(initial.Length);
char startRemoved = removed[0];
int[] stack = new int[initial.Length + 1];
int stackIdx = 0;
foreach (char ch in initial)
{
sb.Append(ch);
// Since all characters in removed are distinct, a match for removed[0] starts a new match
if (ch == startRemoved) stack[++stackIdx] = 1;
// A match for the next character expected extends the current match
else if (ch == removed[stack[stackIdx]]) ++stack[stackIdx];
// And any other character blocks everything up to now from being part of a match
else stackIdx = 0;
if (stack[stackIdx] == removed.Length)
{
--stackIdx;
sb.Length -= removed.Length;
}
}
return sb.ToString();
}
Messing around with the GC settings is a big red flag. If you think that's necessary for a programming challenge then you should instead look at the algorithm.
Sylvain Boisse makes a very good observation about the importance of the guarantee that
The characters in the substring are all different
and a good suggestion to use a stack. Observe that if we encounter a character which neither starts a potential match nor continues the current potential match then it blocks all (unremoved) characters before it from being part of a word, since they would have to span it. Therefore the stack can be clearer, and the code can be remarkably simple.
static string RepeatedRemoval(string initial, string removed)
{
if (removed.Length == 0) return initial;
StringBuilder sb = new StringBuilder(initial.Length);
char startRemoved = removed[0];
// The main case
int[] stack = new int[initial.Length + 1];
int stackIdx = 0;
foreach (char ch in initial)
{
sb.Append(ch);
// Since all characters in removed are distinct, a match for removed[0] starts a new match
if (ch == startRemoved) stack[++stackIdx] = 1;
// A match for the next character expected extends the current match
else if (ch == removed[stack[stackIdx]]) ++stack[stackIdx];
// And any other character blocks everything up to now from being part of a match
else stackIdx = 0;
if (stack[stackIdx] == removed.Length)
{
--stackIdx;
sb.Length -= removed.Length;
}
}
return sb.ToString();
}
A minor optimisation can be obtained by handling the case removed.Length == 1 specially.
static string RepeatedRemoval(string initial, string removed)
{
if (removed.Length == 0) return initial;
StringBuilder sb = new StringBuilder(initial.Length);
char startRemoved = removed[0];
if (removed.Length == 1)
{
foreach (char ch in initial)
{
if (ch != startRemoved) sb.Append(ch);
}
return sb.ToString();
}
// The main case
int[] stack = new int[initial.Length + 1];
int stackIdx = 0;
foreach (char ch in initial)
{
sb.Append(ch);
// Since all characters in removed are distinct, a match for removed[0] starts a new match
if (ch == startRemoved) stack[++stackIdx] = 1;
else if (ch == removed[stack[stackIdx]])
{
// Extend the match by one char, and if it's a full match then pop.
if (++stack[stackIdx] == removed.Length)
{
--stackIdx;
sb.Length -= removed.Length;
}
}
// This char blocks everything up to now from being part of a match
else stackIdx = 0;
}
return sb.ToString();
}