Repeatedly eliminate a substring I'm trying to pass a programming challenge where we are to replace all instances of a substring in a string until there are none left. So an input like


 Pibabakekezza
 bake



Has output


Pizza



And if there is nothing left say so. I fail an unknown test case because I take longer than 1 second. 

//Rextester.Program.Main is the entry point for your code. Don't change it.
//Compiler version 4.0.30319.17929 for Microsoft (R) .NET Framework 4.5

using System;
using System.Runtime;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;
using System.Runtime.CompilerServices;

namespace Rextester
{
    public class Program
    {
        public static void Main(string[] args)
        {
            GCLatencyMode oldMode = GCSettings.LatencyMode;

            // Make sure we can always go to the catch block, 
            // so we can set the latency mode back to `oldMode`
            RuntimeHelpers.PrepareConstrainedRegions();

            try
            {
                GCSettings.LatencyMode = GCLatencyMode.LowLatency;
                //Your code goes here
                string s =Console.ReadLine();
                string b =Console.ReadLine();
                while(s.Contains(b))
                {
                    s=s.Replace(b, "");
                }
                if(s!="")
                {
                    Console.WriteLine(s);
                }
                else
                {
                    Console.WriteLine("FRULA");
                }
            }
            finally
            {
                // ALWAYS set the latency mode back
                GCSettings.LatencyMode = oldMode;
            }
        }
    }
}


Restrictions:

1≤|bigString|≤1 000 000

1≤|substring|≤36

bigString and the substring string consist of uppercase and lowercase letters of the English alphabet and digits 0, 1, …, 9. The characters in the substring are all different.

CPU Time limit: 1 second
Memory limit: 1024 MB
As stated by 200_success +1 string is immutable  

StringBuilder also has Replace but getting it to loop is trickier
You would need to time this  

string s = "Pibabakekezza";
string r = "bake";
StringBuilder sb = new StringBuilder(s);
while (sb.Length != sb.Replace(r, "").Length) { }
Debug.WriteLine(sb.ToString());


A character can only be:


start of replace
in replace
other


Not real clean code - this is more just the algorithm
I know should use { } on every if else
Store partial matches in a Stack
I tested with a very large hard input and it was 40 milliseconds 

public static void QuickReplaceTest()
{
    string s = "Pibabakekezza";
    string r = "bake";
    Debug.WriteLine(QuickReplace2(s, r));
    Debug.WriteLine(QuickReplace3(s, r));

    s = "babakekePbakeibabbakeakebakekezbakezabake";
    r = "b";
    Debug.WriteLine(QuickReplace2(s, r));
    Debug.WriteLine(QuickReplace3(s, r));

    StringBuilder sb = new StringBuilder();
    sb.Append("piz");
    for (int i = 0; i &lt; 100000; i++)
        sb.Append("qrsuvw");
    //sb.Append("piz");
    for (int i = 0; i &lt; 100000; i++)
        sb.Append("xyz");
    sb.Append("za");
    s = sb.ToString();
    sb.Clear();
    r = "qrsuvwxyz";
    Debug.WriteLine(QuickReplace2(s, r));
    Debug.WriteLine(QuickReplace3(s, r));

    s = s.Insert(400000, "pie");
    Debug.WriteLine(QuickReplace2(s, r));
    Debug.WriteLine(QuickReplace3(s, r));

}
public static string QuickReplace2(string s, string r)
{ 
    if(string.IsNullOrEmpty(r))
        return string.Empty;
    if (string.IsNullOrEmpty(s))
        return string.Empty;
    s = s.Trim();
    r = r.Trim();
    if (r.Length &gt; s.Length)
        return string.Empty;
    if (r.Length == 1)
        return(s.Replace(r, ""));

    StringBuilder sb = new StringBuilder(s.Length / 2);
    char[] rArray = r.ToCharArray();
    int rArrayLen = rArray.Length;
    Stack&lt;byte&gt; partialMatches = new Stack&lt;byte&gt;();   
    byte curMatchCount = 0;
    Stopwatch sw = new Stopwatch();
    sw.Start();
    foreach(char c in s)
    {
        //Debug.WriteLine(c);
        if (c == rArray[0])
        {
            if (curMatchCount &gt; 0)
                partialMatches.Push(curMatchCount);
            curMatchCount = 1;
        }
        else if (c == rArray[curMatchCount])
        {
            curMatchCount++;
            if (curMatchCount == rArrayLen)
            {
                if (partialMatches.Count == 0)
                    curMatchCount = 0;
                else
                    curMatchCount = partialMatches.Pop();
            }
        }
        else
        {
            //need to unload the stack
            if (partialMatches.Count &gt; 0)
            {
                foreach (int count in partialMatches.Reverse())
                    for (int i = 0; i &lt; count; i++)
                        sb.Append(rArray[i]);
                partialMatches.Clear();
            }
            for (int i = 0; i &lt; curMatchCount; i++)
                sb.Append(rArray[i]);
            curMatchCount = 0;
            sb.Append(c);
        }
    }
    if (partialMatches.Count &gt; 0)
    {
        foreach (int count in partialMatches.Reverse())
            for (int i = 0; i &lt; count; i++)
                sb.Append(rArray[i]);
    }
    for (int i = 0; i &lt; curMatchCount; i++)
        sb.Append(rArray[i]);
    sw.Stop();
    Debug.WriteLine(sw.ElapsedMilliseconds.ToString());
    return sb.ToString();
}
public static string QuickReplace3(string s, string r)
{
    if (string.IsNullOrEmpty(r))
        return string.Empty;
    if (string.IsNullOrEmpty(s))
        return string.Empty;
    s = s.Trim();
    r = r.Trim();
    if (r.Length &gt; s.Length)
        return string.Empty;
    if (r.Length == 1)
        return (s.Replace(r, ""));

    StringBuilder sb = new StringBuilder(s.Length / 2);
    char[] rArray = r.ToCharArray();
    int rArrayLen = rArray.Length;
    Stack&lt;byte&gt; partialMatches = new Stack&lt;byte&gt;();
    byte curMatchCount = 0;
    Stopwatch sw = new Stopwatch();
    sw.Start();
    foreach (char c in s)
    {
        sb.Append(c);
        if (c == rArray[0])
        {
            if (curMatchCount &gt; 0)
                partialMatches.Push(curMatchCount);
            curMatchCount = 1;
        }
        else if (c == rArray[curMatchCount])
        {
            curMatchCount++;
            if (curMatchCount == rArrayLen)
            {
                sb.Length -= rArrayLen;
                if (partialMatches.Count == 0)
                    curMatchCount = 0;
                else
                    curMatchCount = partialMatches.Pop();
            }
        }
        else
        {
            curMatchCount = 0;
            partialMatches.Clear();
        }
    }
    sw.Stop();
    Debug.WriteLine(sw.ElapsedMilliseconds.ToString());
    return sb.ToString();
}