NeetCode #771LC-3223MediumGreedy
← Back to All Problems#771 · #3223 · Minimum Length of String After Operations(操作后字符串的最短长度)
📌 Problem Statement & Constraints
Given a string
s, an operation picks an index i and a character c equal to s[i] that appears both to the left and to the right of i, then deletes the closest such occurrence on each side. Return the minimum length of s after any number of operations. Constraints: 1 <= s.length <= 2 * 10^5, s consists of lowercase English letters.💡 Core Algorithmic Approaches
- Operations on different characters are independent, so the total minimum is the sum over characters.
- For a character with frequency
f < 3, no operation is possible, so it contributesf. - For
f >= 3, each operation removes two copies of the same character, so the parity offis preserved. - The minimum reachable count is 1 when
fis odd and 2 whenfis even.
💻 Benchmark Python3 Implementation
class Solution:
def minimumLength(self, s: str) -> int:
from collections import Counter
res = 0
for f in Counter(s).values():
if f >= 3:
res += 1 if f % 2 else 2
else:
res += f
return res⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): one pass to count plus one over the alphabet.
💾 Space Complexity
O(1): at most 26 frequency entries.
⚠️ Interview Pitfalls & Follow-ups
- Reducing a frequency of 2: two copies cannot be reduced because an operation needs a matching character on both sides.
- Getting the parity backwards: an odd count reduces to 1, an even count to 2.
- Thinking characters interact: operations on one character never affect another character's count.
- Assuming a frequency of 1 can be removed: a single occurrence has no pair to delete.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.