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

Minimize String Length

Number: 2825

Difficulty: Easy

Paid? No

Companies: N/A

Problem Description

Given a string s, you can perform operations to delete duplicate occurrences. Specifically, for any index i with character c, you can delete the closest occurrence of c either to its left or right (if it exists). The goal is to minimize the string's length by performing these operations any number of times.

Key Insights

  • The operations allow you to remove duplicate characters one by one.
  • The minimal string obtained will contain at most one occurrence of every character.
  • Therefore, the answer is the number of distinct characters in the string.
  • Using a set to track unique characters is ideal since there are only 26 lowercase English letters at most.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string, as we iterate through all characters. Space Complexity: O(1), because there are at most 26 unique characters regardless of n.

Solution

The key idea is that after repeatedly performing the allowed deletion operations, every duplicate can be removed until only one copy of each character remains. Hence, the minimal possible string length is simply the count of unique characters in s. A set is used to efficiently track these unique characters, leading to an O(n)-time solution with constant space relative to the input size.

Code Solutions

# Python solution
def minimizeStringLength(s):
    # Use a set to get all unique characters in the string.
    unique_chars = set(s)
    # The minimum length is the number of unique characters.
    return len(unique_chars)

# Example usage:
print(minimizeStringLength("aaabc"))  # Output: 3
← Back to All Questions