Minimum Length of String After Operations

Medium
1027.

Minimum Length of String After Operations

Minimum Length of String After Operations is a medium coding problem on strings, hash table and counting, asked in Amazon, Google and Salesforce interviews.

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.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @return {number}
 */
var minimumLength = function(s) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Minimum Length of String After Operations — Solution

Minimum Length of String After Operations solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Minimum Length of String After Operations is a medium coding problem on strings, hash table and counting, asked in Amazon, Google and Salesforce interviews.

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.

Hints for Minimum Length of String After Operations

  1. Hint 1

    Each operation removes two copies of one letter, and letters never interfere with each other.

  2. Hint 2

    So ask, per letter: how few copies can k occurrences be reduced to?

  3. Hint 3

    Operating needs three copies, and each operation removes two — so the parity of the count is the whole answer.

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)

Java

public static int minimumLength(String s) {
    int[] cnt = new int[26];
    for (int i = 0; i < s.length(); i++) cnt[s.charAt(i) - 'a']++;
    int total = 0;
    for (int k : cnt) {
        if (k == 0) continue;
        total += k % 2 == 1 ? 1 : 2;
    }
    return total;
}

C++

int minimumLength(string s) {
    vector<int> cnt(26, 0);
    for (char c : s) cnt[c - 'a']++;
    int total = 0;
    for (int k : cnt) {
        if (k == 0) continue;
        total += k % 2 == 1 ? 1 : 2;
    }
    return total;
}

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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Hashing: Hash Maps and Hash Sets