Problem Description

You are given a string s and can perform two types of operations on it:

1. Delete left neighbor: Choose an index i in the string. Let c be the character at position i. Delete the closest occurrence of character c that appears to the left of position i (if such an occurrence exists).

2. Delete right neighbor: Choose an index i in the string. Let c be the character at position i. Delete the closest occurrence of character c that appears to the right of position i (if such an occurrence exists).

You can perform these operations zero or more times in any order. Your goal is to minimize the length of the string after performing these operations.

Return the minimum possible length of the string.

Key Insight: When you choose a character at position i, you can delete another occurrence of the same character either to its left or right. This means that for any character that appears multiple times, you can keep reducing its occurrences until only one remains. No matter which occurrences you choose to delete or in what order, you'll always end up with at least one occurrence of each distinct character. Since you cannot delete the last remaining occurrence of any character (there would be no matching character to the left or right), the minimum length equals the number of distinct characters in the string.

For example, if s = "aaabc", you can:

• Choose index 1 (character 'a'), delete the 'a' at index 0
• Choose index 1 (character 'a'), delete the 'a' at index 2
• Final string: "abc" with length 3

The solution simply returns len(set(s)), which counts the number of unique characters in the string.

Intuition

Let's think about what happens when we perform these operations. When we select a character at position i, we can only delete another occurrence of the same character - either to its left or right. This is the crucial observation.

Consider a character that appears multiple times in the string, say 'a' appears 5 times. By repeatedly choosing positions with 'a' and deleting neighboring 'a's, we can reduce the count from 5 → 4 → 3 → 2 → 1. But we can never go from 1 → 0, because when only one 'a' remains, there's no other 'a' to its left or right to delete.

This pattern holds for every distinct character in the string. No matter how many times a character appears initially, we can always reduce it down to exactly one occurrence, but never to zero.

Let's trace through another example: s = "aabcbaa"

• Character 'a' appears 4 times → can be reduced to 1
• Character 'b' appears 2 times → can be reduced to 1
• Character 'c' appears 1 time → stays at 1 (can't delete it)

The minimum possible string would have exactly one occurrence of each distinct character: one 'a', one 'b', and one 'c', giving us a length of 3.

This leads us to realize that the minimum length is simply the count of distinct characters in the original string. The order of operations doesn't matter - we'll always end up with the same minimum length. That's why the solution is elegantly simple: len(set(s)), which counts the unique characters.

Solution Approach

The solution uses a hash table (or set) data structure to count the number of distinct characters in the string. This is the most straightforward approach once we understand that the problem reduces to finding unique characters.

Implementation Details:

The Python solution leverages the built-in set() data structure:

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

Here's how it works:

1. Convert string to set: set(s) creates a set from the string s. When a string is converted to a set, it automatically removes all duplicate characters, keeping only one instance of each unique character.

2. Count unique elements: len(set(s)) returns the size of the set, which equals the number of distinct characters.

Why this works:

• A set is an unordered collection that stores only unique elements
• When we pass a string to set(), it iterates through each character and adds it to the set
• Duplicate characters are automatically ignored (set property)
• The resulting set contains exactly one instance of each distinct character

Time Complexity: O(n) where n is the length of the string, as we need to iterate through all characters once to build the set.

Space Complexity: O(k) where k is the number of distinct characters in the string. In the worst case where all characters are unique, k = n, giving us O(n) space complexity.

This approach is optimal because we must examine every character at least once to determine the distinct characters, and the set provides the most efficient way to track uniqueness.

Example Walkthrough

Let's walk through the solution with the string s = "abbaca".

Step 1: Identify the distinct characters

• The string contains: 'a' (appears 3 times), 'b' (appears 2 times), 'c' (appears 1 time)

Step 2: Understanding possible operations

• We can choose any 'a' and delete another 'a' to its left or right
• We can choose any 'b' and delete another 'b' to its left or right
• We cannot delete 'c' since there's only one occurrence

Step 3: Simulating the reduction process

Starting string: "abbaca" (length 6)

One possible sequence of operations:

• Choose index 0 ('a'), delete the 'a' at index 3 → "bbbca" (length 5)
• Choose index 0 ('b'), delete the 'b' at index 1 → "bbca" (length 4)
• Choose index 3 ('a'), delete the 'a' at index 2 → "bbc" (length 3)

We're left with one 'b' and one 'c', but we still have an 'a' at the end that we haven't accounted for. Let me reconsider:

Starting string: "abbaca" (length 6)

• Choose index 3 ('a'), delete the 'a' at index 0 → "bbaca" (length 5)
• Choose index 3 ('a'), delete the 'a' at index 2 → "bbca" (length 4)
• Choose index 0 ('b'), delete the 'b' at index 1 → "bca" (length 3)

Final result: "bca" - exactly one of each distinct character!

Step 4: Apply the solution approach

s = "abbaca"
unique_chars = set(s)  # {'a', 'b', 'c'}
result = len(unique_chars)  # 3

The set automatically identifies the 3 distinct characters ('a', 'b', 'c'), giving us the minimum possible length of 3. This matches what we achieved through manual operations, confirming that no matter how we perform the deletions, we'll always end up with at least one of each distinct character.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the string s. This is because converting a string to a set requires iterating through each character in the string exactly once to build the set.

The space complexity is O(|Σ|), where Σ is the character set. Since the problem deals with lowercase English letters, |Σ| = 26. In the worst case, the set will contain at most 26 unique characters regardless of the input string length, making the space complexity O(26) which simplifies to O(1) constant space.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Misunderstanding the Problem as a Greedy Deletion Problem

The Mistake: Many developers initially approach this problem by trying to implement the actual deletion operations, thinking they need to:

• Track indices and perform actual deletions
• Decide which neighbor (left or right) to delete for optimal results
• Maintain the string state after each operation

Example of Incorrect Approach:

def minimizedStringLength(self, s: str) -> int:
    s_list = list(s)
    changed = True
    while changed:
        changed = False
        for i in range(len(s_list)):
            if s_list[i] is None:
                continue
            # Try to find and delete left neighbor
            for j in range(i-1, -1, -1):
                if s_list[j] == s_list[i]:
                    s_list[j] = None
                    changed = True
                    break
            # Complex logic continues...
    return len([c for c in s_list if c is not None])

Why This is Wrong: This approach is unnecessarily complex and inefficient. The problem doesn't require simulating the operations; it only asks for the final minimum length.

The Solution: Recognize that regardless of the order of operations, you can always reduce any character that appears multiple times down to a single occurrence. The key insight is that the minimum length is simply the count of distinct characters.

Pitfall 2: Overthinking Edge Cases

The Mistake: Worrying about special scenarios like:

• What if the string has only one character repeated multiple times?
• What about the order of characters after operations?
• Should we preserve the relative positions of remaining characters?

Example Concern:

# Unnecessary edge case handling
def minimizedStringLength(self, s: str) -> int:
    if len(s) == 0:
        return 0
    if len(s) == 1:
        return 1
    if all(c == s[0] for c in s):  # All same character
        return 1
    # ... more unnecessary checks
    return len(set(s))

Why This is Wrong: The set() approach naturally handles all these cases:

• Empty string: set("") returns an empty set with length 0
• Single character: set("a") returns a set with one element
• All same characters: set("aaaa") returns a set with one element
• Mixed characters: Works correctly for any combination

The Solution: Trust that the mathematical property (minimum length = distinct characters) applies universally without special cases.

Pitfall 3: Using Inefficient Data Structures

The Mistake: Using a dictionary or manual counting instead of a set:

def minimizedStringLength(self, s: str) -> int:
    char_count = {}
    for char in s:
        char_count[char] = char_count.get(char, 0) + 1
    return len(char_count)

Or using a list to track unique characters:

def minimizedStringLength(self, s: str) -> int:
    unique = []
    for char in s:
        if char not in unique:
            unique.append(char)
    return len(unique)

Why This is Suboptimal:

• The dictionary approach wastes space storing counts we don't need
• The list approach has O(n²) time complexity due to the in operation being O(n) for lists

The Solution: Use set(s) which is specifically designed for tracking unique elements with O(1) average-case insertion and lookup, making it both the simplest and most efficient approach.