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
- Two pointers at the ends. While the end characters match, greedily consume the entire run of that character from both ends.
- Each iteration removes a maximal prefix run and a maximal suffix run of the same character.
- The pointers meet or cross when no further deletion is possible, and the remaining length is
r - l + 1. - 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 < ras the inner loop condition: the runs may overlap, so the guard must bel <= rto 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 isr - 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.