#2716

Easy

LeetCode Problem Workspace

Minimize String Length

Minimize String Length asks you to reduce a string by removing duplicates using a Hash Table strategy efficiently.

Problem Statement

Given a string s consisting of lowercase English letters, you can perform two operations: remove any character, or remove a character if it is a duplicate of another. Your goal is to apply these operations to minimize the length of s.

Return the length of the minimized string after performing zero or more operations. For example, for s = "aaabc", the minimized length is 3 because only distinct letters remain.

Examples

Example 1

Input: s = "aaabc"

Output: 3

Example 2

Input: s = "cbbd"

Output: 3

Example 3

Input: s = "baadccab"

Output: 4

Constraints

1 <= s.length <= 100
s contains only lowercase English letters

Solution Approach

Use a Hash Set to Track Unique Letters

Iterate through the string and add each character to a hash set. Since sets automatically ignore duplicates, the size of the set after processing is the minimized string length.

Count Unique Characters Directly

Maintain an array of 26 elements for each lowercase letter and mark presence. Increment a counter for each distinct letter. This avoids storing strings and directly computes minimized length.

Return the Count as Result

After processing the string with the hash set or array, the count of unique characters represents the minimized string length, which is returned as the final answer.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) since each character is processed once. Space complexity is O(1) with a fixed 26-letter array or O(k) for a hash set storing k unique letters.

What Interviewers Usually Probe

Focus on identifying unique characters efficiently.
Expect a simple hash table or set-based solution for string reduction.
Watch for off-by-one errors when counting duplicates.

Common Pitfalls or Variants

Common pitfalls

Trying to remove duplicates manually with nested loops, leading to O(n^2) time.
Forgetting that only the count of unique characters matters, not their order.
Using extra memory unnecessarily instead of a fixed-size array or set.

Follow-up variants

Minimize string length for uppercase letters using a similar hash table approach.
Return the minimized string itself instead of just the length.
Count unique characters after allowing limited repeated removals or restricted operations.

FAQ

What is the main trick in Minimize String Length?

The key is using a hash set or fixed array to track unique letters, since the minimized string length equals the number of distinct characters.

Can this approach handle strings up to length 100 efficiently?

Yes, iterating once with a set or array provides O(n) time complexity, easily handling strings of length up to 100.

Do I need to preserve the original order of characters?

No, only the count of unique letters matters. Order is irrelevant for minimized length.

Is using a hash table always better than sorting?

Yes, because sorting adds O(n log n) overhead while a hash set counts unique letters in O(n).

Does this solution apply to other string minimization problems?

Yes, any problem where duplicates are removed to minimize length can use the Hash Table plus String pattern efficiently.

terminal

Solution

Solution 1: Hash Table

The problem can actually be transformed into finding the number of distinct characters in the string. Therefore, we only need to count the number of distinct characters in the string.

1

2

3

class Solution:
    def minimizedStringLength(self, s: str) -> int:
        return len(set(s))

Continue Practicing

#2707 extra characters in a string #2744 find maximum number of string pairs #2767 partition string into minimum beautiful substrings