⚡Flashcard Drill➔
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

  1. Operations on different characters are independent, so the total minimum is the sum over characters.
  2. For a character with frequency f < 3, no operation is possible, so it contributes f.
  3. For f >= 3, each operation removes two copies of the same character, so the parity of f is preserved.
  4. The minimum reachable count is 1 when f is odd and 2 when f is 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.
🎯 Drill This Card Now➔

🧩 Related Greedy Problems