字符串相邻重复字符移除函数性能优化方案咨询

Hey there! Let's dig into why your current code isn't as performant as it could be, and walk through some better approaches.

The Problem with Your Current Implementation #

Your core logic for skipping adjacent duplicates is correct, but the bottleneck comes from using String response = "" and doing response += temp repeatedly.

In Java, Strings are immutable—every time you use +=, you're actually creating a brand new String object that copies all the existing characters plus the new one. For a string of length n, this leads to a worst-case time complexity of O(n²) (since each copy operation takes O(k) time where k is the current length of the string). For large input strings, this gets slow fast.

Fix 1: Use StringBuilder for Mutable String Construction #

The simplest fix is to replace the immutable String with a StringBuilder, which is designed for efficient appends and modifications. Here's how your code would look with this change:

public String remdups(String input) {
    if (input == null || input.isEmpty()) {
        return input;
    }
    
    StringBuilder response = new StringBuilder();
    char temp = input.charAt(0);
    response.append(temp);
    
    for (int i = 1; i < input.length(); i++) {
        char current = input.charAt(i);
        if (current != temp) {
            response.append(current);
            temp = current;
        }
    }
    
    return response.toString();
}

Why This Works Better: #

• StringBuilder's append() operation runs in amortized O(1) time (it only resizes its internal array when it runs out of space, which happens rarely).
• This brings the overall time complexity down to O(n), since we iterate through the input exactly once, with each character processed in constant time.
• We also added null/empty input checks to make the function more robust.

Fix 2: Use a Stack for Intuitive Logic (Great for Extensibility) #

If you want a more readable approach that's easier to extend (e.g., if you later need to remove sequences of k adjacent duplicates), using a stack is a great option. Here's how that works:

import java.util.Deque;
import java.util.ArrayDeque;

public String remdups(String input) {
    if (input == null || input.isEmpty()) {
        return input;
    }
    
    Deque<Character> stack = new ArrayDeque<>();
    
    for (char c : input.toCharArray()) {
        if (!stack.isEmpty() && stack.peek() == c) {
            continue; // Skip duplicate
        }
        stack.push(c);
    }
    
    // Build the result string from the stack
    StringBuilder result = new StringBuilder();
    while (!stack.isEmpty()) {
        result.append(stack.pop());
    }
    return result.reverse().toString();
}

Why This Works: #

• We iterate through each character once (O(n) time), and stack operations (push, peek, pop) are O(1).
• The logic is straightforward: we only keep a character if it doesn't match the one at the top of our stack.
• This approach scales well if you need to handle more complex duplicate rules (like removing 3+ adjacent duplicates later).

Testing with Your Example #

Both implementations will correctly process your input:

Input: "aabbaabbcccaaa"
Output: "ababca"

Performance Comparison #

• The StringBuilder approach is slightly more efficient in practice, as it avoids the stack's reverse step and has minimal overhead.
• The stack approach is more readable and flexible for future changes.

Choose whichever fits your needs best—both are O(n) time and O(n) space (since we store the result, which can be up to the length of the input in the best case where there are no duplicates).

内容的提问来源于stack exchange，提问作者Rafael Gonçalves