Minimum Length of String After Operations

medium hash table string counting

Problem

Given a string s, you may repeatedly pick an index i that has at least one equal character to its left and at least one equal character to its right, then delete the closest matching character on each side (two deletions, while s[i] stays). Return the minimum length the string can reach.

Only the frequency of each letter matters. Each operation on a letter removes exactly two of its copies, so a letter's count keeps dropping by 2 while it is still ≥ 3. The number of survivors is therefore 1 when the count is odd and 2 when the count is even.

Inputs = "abaacbcbb"

Output5

a appears 3× (odd → 1), b appears 4× (even → 2), c appears 2× (even → 2): 1 + 2 + 2 = 5.

s (lowercase letters)

def minimumLength(s):
    freq = {}                         # hash map: letter -> count
    for ch in s:
        freq[ch] = freq.get(ch, 0) + 1
    total = 0
    for ch, f in freq.items():
        # odd count collapses to 1, even count to 2
        total += 1 if f % 2 == 1 else 2
    return total

function minimumLength(s) {
  const freq = new Map();             // hash map: letter -> count
  for (const ch of s) {
    freq.set(ch, (freq.get(ch) || 0) + 1);
  }
  let total = 0;
  for (const f of freq.values()) {
    // odd count collapses to 1, even count to 2
    total += f % 2 === 1 ? 1 : 2;
  }
  return total;
}

int minimumLength(String s) {
    int[] freq = new int[26];         // count table for a..z
    for (char ch : s.toCharArray()) {
        freq[ch - 'a']++;
    }
    int total = 0;
    for (int f : freq) {
        if (f == 0) continue;
        // odd count collapses to 1, even count to 2
        total += (f % 2 == 1) ? 1 : 2;
    }
    return total;
}

int minimumLength(string s) {
    int freq[26] = {0};               // count table for a..z
    for (char ch : s) {
        freq[ch - 'a']++;
    }
    int total = 0;
    for (int f : freq) {
        if (f == 0) continue;
        // odd count collapses to 1, even count to 2
        total += (f % 2 == 1) ? 1 : 2;
    }
    return total;
}

Explanation

The operation looks positional, but it is really about counts. When you choose index i, the chosen character s[i] is kept, while one matching copy on the left and one on the right are deleted. So a single operation always removes exactly two copies of one letter, and it is allowed only while that letter has at least three copies (one in the middle plus one on each side).

Different letters never interfere — deleting copies of a changes nothing about how many bs remain. So we can treat every letter independently. Build a frequency hash map in one pass over s.

For a letter with count f, keep applying the operation: each time, f drops by 2. You can do this while f ≥ 3, so it bottoms out at 1 if f was odd, or 2 if f was even. Letters with f = 1 or f = 2 already cannot move and follow the same rule.

Therefore each distinct letter contributes 1 to the answer when its count is odd and 2 when its count is even. Sum those contributions across all letters present in the map.

Example s = "abaacbcbb": counts are a=3, b=4, c=2. Odd 3 → 1, even 4 → 2, even 2 → 2, total 1 + 2 + 2 = 5.

Time: O(n) Space: O(1) (26 letters)