Get started

Minimum Length of String After Operations — Medium Problem & Solution

Repeatedly apply this operation as long as it is possible: choose an index i such that there is at least one character equal to s[i] to its left and at…

Problem statement

Repeatedly apply this operation as long as it is possible:

  • choose an index i such that there is at least one character equal to s[i] to its left and at least one to its right;
  • delete the closest such character on the left and the closest on the right.

Return the minimum length s can reach.

Example 1

Input: s = "codekairocodekairo"
Output: 16
Explanation: Every letter appears exactly twice, and a letter needs three copies before anything can be deleted.

Example 2

Input: s = "abaacbcbb"
Output: 5
Explanation: `a` occurs 3 times and drops to 1; `b` (4) and `c` (2) each keep 2.

Example 3

Input: s = "aa"
Output: 2
Explanation: No index has a matching character on **both** sides.

Constraints

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

How to solve Minimum Length of String After Operations

The operation only ever removes two copies of a single letter, so each letter can be reasoned about independently. A letter with k occurrences can be reduced while k >= 3, two at a time — so it settles at 1 if k is odd and 2 if k is even. Sum those per-letter residues.

Approach

  1. Tally the 26 letter counts.
  2. For each letter present, add 1 if its count is odd and 2 if it is even.
  3. Return the sum.

Why it works

Two facts make this a counting problem rather than a simulation. First, the deleted pair always matches s[i], so no letter's count is affected by another's. Second, an operation is available for a letter as soon as it has three copies, and removing two keeps that available until only one or two remain — so the reachable minimum is determined entirely by parity, not by the order of operations or the positions of the letters.

Complexity

  • Time — O(n)
  • Space — O(1) — a 26-slot tally

Pitfalls

  • A letter with count 2 cannot be reduced at all; only three or more can.
  • Letters absent from s contribute nothing, not 2.
  • Simulating the deletions is unnecessary and quadratic at the upper bound.

Reference solution

Python

def minimumLength(s: str) -> int:
    cnt = [0] * 26
    for c in s:
        cnt[ord(c) - 97] += 1
    return sum(1 if k % 2 == 1 else 2 for k in cnt if k > 0)

JavaScript

var minimumLength = function(s) {
    var cnt = [], i;
    for (i = 0; i < 26; i++) cnt.push(0);
    for (i = 0; i < s.length; i++) cnt[s.charCodeAt(i) - 97]++;
    var total = 0;
    for (i = 0; i < 26; i++) {
        if (cnt[i] === 0) continue;
        total += cnt[i] % 2 === 1 ? 1 : 2;
    }
    return total;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 282 strings problems · the whole catalogue