Repeatedly eliminate a substring
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();
}