Skip to content

Practice Minimum Length of String After Operations

Read the task, work through the examples, and check your approach against the constraints. Use the original LeetCode task for coding and submissions.

Medium#3223
LeetCode Problem

Minimum Length of String After Operations

Problem Statement

In one operation on s, choose a character that has an equal character somewhere on both its left and its right. Delete the nearest matching character on each side, keeping the chosen character. Repeat any number of times and return the smallest possible remaining length.

Source: Minimum Length of String After Operations on LeetCode. Use the original task for its coding environment and submissions.

Examples

# Example 1

Input
s = "abaacbcbb"
Output
5
Explanation

There are three a's, four b's and two c's. Each operation removes two occurrences of one letter while keeping its chosen occurrence, so an odd positive count can shrink to 1 and an even positive count to 2. The lower bound is therefore 1 + 2 + 2 = 5. It is attainable: choose the a at index 2 to obtain "bacbcbb", then choose the b at index 3 of that new string to obtain "acbcb". Each choice removes the nearest matching letter on either side. Counts of 1 or 2 cannot shrink further because a valid choice needs three occurrences.

# Example 2

Input
s = "aa"
Output
2
Explanation

Neither a has an a on both its left and its right. No operation is legal, so the string stays "aa" and its length is 2. Although one operation deletes two matching letters, it also requires a third matching letter to remain as the chosen center. Do not subtract two merely because the frequency is even; an even positive frequency bottoms out at 2, not 0.

Constraints

1 <= s.length <= 2 * 10^5
s consists only of lowercase English letters.

How to solve Minimum Length of String After Operations

Original notes for interview preparation, written for this problem. Reviewed .

Key insight

Positions never matter, only counts: every operation removes exactly two copies of one letter and needs a third copy as the center, so a letter with count c shrinks to 1 if c is odd and to 2 if c is even, never further. The answer is the sum of those floor values over letters present.

Why brute force is not enough

Simulating deletions on the string, repeatedly finding a character with matches on both sides and removing the nearest ones, is O(n) per operation over up to O(n) operations, about 4 * 10^10 steps for s.length up to 2 * 10^5.

Approach

  1. Count occurrences of each of the 26 letters in one pass.
  2. Argue that any letter with at least three occurrences admits an operation: pick an occurrence that is neither leftmost nor rightmost of that letter, and it has a match on each side. Each operation lowers that count by exactly 2 and leaves other letters untouched.
  3. Conclude the process for a letter stops when its count drops below 3, so odd counts end at 1 and even positive counts at 2; parity of every count is invariant across operations.
  4. Sum the final counts over all letters, or equivalently subtract from the length twice the total of floor((c - 1) / 2) over letters.

Walkthrough of Example 1

s = "abaacbcbb" → 5

  1. Counts in abaacbcbb: a appears 3 times, b 4 times, c 2 times.
  2. a is odd at 3, shrinks once and ends at 1.
  3. b is even at 4, shrinks once and ends at 2; another operation would need three b's.
  4. c is already below 3 and stays at 2.
  5. Minimum length 1 + 2 + 2 = 5.

Time and space

Time O(n) · Space O(1). One pass over the n characters builds the counts, and the 26-entry frequency table is constant extra space.

Interview pitfalls

  • Reducing an even count to 0; two copies cannot form a center with a match on both sides, so even counts bottom out at 2.
  • Assuming adjacency or positions constrain the result; any middle occurrence works, so only counts matter.
  • Simulating deletions with repeated slicing, which is quadratic and unnecessary.
  • Adding 2 for every letter of the alphabet rather than only letters with a positive count.

Follow-up questions interviewers ask

  • What if an operation deleted the chosen character together with its two neighbors, lowering counts by 3?
  • How would you report the actual sequence of operations rather than just the final length?
  • If characters arrive as a stream, how would you maintain the current minimum length in O(1) per append?

Related LeetCode Problems

Practice more problems similar to Minimum Length of String After Operations.

Review your practice with PhantomCodeAI

After trying the problem yourself, use the app to discuss your approach, complexity, and edge cases.