⚡Flashcard Drill➔
NeetCode #212LC-1750MediumTwo Pointers
← Back to All Problems

#212 · #1750 · Minimum Length of String After Deleting Similar Ends(删除字符串两端相同字符后的最短长度)

📌 Problem Statement & Constraints

Given a string s consisting only of characters a, b and c, repeatedly delete a prefix and a suffix that both consist of the same character, until no such pair exists. Return the minimum length of the remaining string. Constraints: 1 <= s.length <= 10^5.

💡 Core Algorithmic Approaches

  1. Two pointers at the ends. While the end characters match, greedily consume the entire run of that character from both ends.
  2. Each iteration removes a maximal prefix run and a maximal suffix run of the same character.
  3. The pointers meet or cross when no further deletion is possible, and the remaining length is r - l + 1.
  4. Consuming maximal runs (rather than one character at a time) is what makes the algorithm O(n) rather than O(n^2).

💻 Benchmark Python3 Implementation

class Solution:
    def minimumLength(self, s: str) -> int:
        l, r = 0, len(s) - 1
        while l < r and s[l] == s[r]:
            ch = s[l]
            while l <= r and s[l] == ch:   # consume the whole prefix run
                l += 1
            while l <= r and s[r] == ch:   # consume the whole suffix run
                r -= 1
        return r - l + 1

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): each character is consumed at most once.
💾 Space Complexity
O(1): two indices.

⚠️ Interview Pitfalls & Follow-ups

  • Deleting one character from each side per iteration: O(n^2) in the worst case; consume maximal runs instead.
  • Using l < r as the inner loop condition: the runs may overlap, so the guard must be l <= r to avoid over-consuming.
  • Forgetting the outer s[l] == s[r] check: without it, unrelated end characters would be consumed.
  • Returning r - l: the remaining length is r - l + 1, and it can be 0 when the pointers cross.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Two Pointers Problems