如何高效去除字符串中的连续重复字符？（面试题）

Great question! Let's break down why your initial approach might have been flagged as "not efficient enough" and then dive into a tighter, optimized solution.

First off, your original code works correctly, but it has a couple of small inefficiencies that could add up with larger strings:

• Calling s.ToCharArray() creates an entirely new array copy of the string, which uses extra O(n) memory unnecessarily.
• The StringBuilder starts with its default initial capacity (16), meaning it will need to resize and copy its internal array multiple times as it grows for longer inputs.

And you’re right—Linq’s Distinct() is totally the wrong tool here because it removes all duplicate characters, not just consecutive ones.

Optimized Implementation #

Here’s a more efficient approach that fixes those gaps while keeping the same optimal O(n) time complexity (you can’t beat O(n) for this problem, since you have to check every character at least once):

private string CollapseConsecutiveDuplicates(string input)
{
    // Handle edge cases first to skip unnecessary work
    if (string.IsNullOrEmpty(input))
        return input;

    // Pre-size StringBuilder to match input length to avoid resizing overhead
    StringBuilder result = new StringBuilder(input.Length);
    char previousChar = input[0];
    result.Append(previousChar);

    // Iterate directly over the string (no need to convert to a char array)
    for (int i = 1; i < input.Length; i++)
    {
        char currentChar = input[i];
        if (currentChar != previousChar)
        {
            result.Append(currentChar);
            previousChar = currentChar;
        }
    }

    return result.ToString();
}

Why This Is Better #

1. No Extra Array Allocation: Instead of converting the string to a char array, we directly access characters via the string’s indexer. Strings in C# are immutable, but their characters can be accessed in O(1) time without copying the entire string.
2. Pre-sized StringBuilder: By setting the initial capacity to input.Length, we ensure the StringBuilder never needs to resize its internal buffer—this eliminates the overhead of repeated array copies that happen when the buffer runs out of space.
3. Early Edge Case Handling: We immediately return empty or null strings instead of entering the loop, saving unnecessary iterations.

Testing with Your Example #

If you pass "reeeturrrnneedd" to this method, it will correctly return "returned"—just like your original code, but with less memory overhead and faster execution for large strings.

What About Linq? #

While you could use Linq to solve this (like with Aggregate), it’s not efficient. For example:

var linqResult = input.Aggregate("", (current, c) => current.EndsWith(c.ToString()) ? current : current + c);

This creates a new string for every character in the input, leading to O(n²) time complexity in the worst case—definitely worse than the straightforward loop approach.

Your core logic was solid; we just trimmed away the unnecessary memory overhead to make it as efficient as possible.

内容的提问来源于stack exchange，提问作者Neeraj Kumar Gupta