We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Length of String After Operations

Number: 3455

Difficulty: Medium

Paid? No

Companies: IBM

Problem Description

Given a string s, you can repeatedly perform the following operation: choose an index i such that there is at least one occurrence of s[i] before i and at least one after i, then remove the closest same-character occurrence to the left of i and the closest same-character occurrence to the right of i. Return the minimum possible length of s after performing any number of operations.

Key Insights

  • The operation only applies when a character appears at least three times.
  • For each letter, you can remove pairs of occurrences (the ones adjacent in the list of occurrences) using one of its occurrences as a “pivot.”
  • For a character with frequency f:
    • If f is less than 3, no removal is possible; the letter remains f times.
    • If f ≥ 3:
      • When f is odd, you can remove pairs until 1 remains.
      • When f is even, you can remove pairs until 2 remain.
  • The operations on different characters do not interact. The final minimal string length is simply the sum of the irreducible counts for each character.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string (we count the frequency of each character). Space Complexity: O(1), since we only maintain a frequency counter for 26 lowercase letters.

Solution

We first count the frequency of each character in the string. For each character:

  • If its frequency is less than 3, add the frequency to the result (no removals possible).
  • If its frequency is 3 or more, then:
    • If the frequency is odd, the minimal residual is 1.
    • If the frequency is even, the minimal residual is 2. The sum of these residuals for all characters gives the minimal length of the final string.

This works because for each character you can remove two copies whenever there is an inner “pivot” occurrence. The removals can be repeated until you can no longer find an occurrence that has both a left and right neighbor with the same character.

Code Solutions

# Python code solution with line-by-line comments

from collections import Counter

def minimumLength(s: str) -> int:
    # Count the frequency of each character in the string
    freq = Counter(s)
    
    # Initialize the minimal length result
    result = 0
    
    # Iterate over each character frequency
    for char, count in freq.items():
        if count < 3:
            # If frequency is less than 3, no removal operation can be applied
            result += count
        else:
            # For frequency 3 or more:
            # If count is odd -> 1 remains; if even -> 2 remain
            result += (1 if count % 2 == 1 else 2)
    
    return result

# Example usage:
print(minimumLength("abaacbcbb"))  # Expected output: 5
print(minimumLength("aa"))         # Expected output: 2
← Back to All Questions