1910. Remove All Occurrences of a Substring

Time: O(n * k)

Space: O(n)

Approach

Use StringBuilder as a virtual stack; after each append, check if suffix matches part and remove.

Key Techniques

String problems range from simple character counting to complex pattern matching. Common approaches include two pointers, sliding window, prefix hashing, and the KMP algorithm. In C#, strings are immutable — use StringBuilder for efficient concatenation inside loops.

1910.cs

// Approach: Use StringBuilder as a virtual stack; after each append, check if suffix matches part and remove.
// Time: O(n * k) Space: O(n)

public class Solution
{
    public string RemoveOccurrences(string s, string part)
    {
        int n = s.Length;
        int k = part.Length;

        StringBuilder sb = new StringBuilder(s);
        int j = 0; // sb's index

        for (int i = 0; i < n; ++i)
        {
            sb[j++] = s[i];
            if (j >= k && sb.ToString().Substring(j - k, k) == part)
                j -= k;
        }

        return sb.ToString().Substring(0, j);
    }
}

Was this solution helpful?