Minimize String Length

Difficulty: Easy | Acceptance: 79.20% | Paid: No Topics: Hash Table, String

Given a string s, you can perform two types of operations on the string:

Remove any character from the string if it appears at least twice.

Return the minimum length of the string after performing the above operations.

Table of Contents

• Examples
• Constraints
• Hash Set
• Boolean Array
• Bit Manipulation

Examples

Input: s = "aaabc"
Output: 3
Explanation: Remove two 'a' characters to get "abc".

Input: s = "cbbd"
Output: 3
Explanation: Remove one 'b' character to get "cbd".

Input: s = "dddaaa"
Output: 2
Explanation: Remove two 'd' and two 'a' characters to get "da".

Constraints

1 <= s.length <= 100
s consists of lowercase English letters.

Hash Set

Intuition The minimum length is achieved by keeping only one instance of every unique character. A Hash Set automatically handles uniqueness.

Steps

• Initialize an empty Hash Set.
• Iterate through each character in the string and add it to the set.
• The size of the set represents the count of unique characters, which is the answer.

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

Complexity

• Time: O(N)
• Space: O(1) (Since the alphabet size is constant 26)
• Notes: High-level abstraction, very readable.

Boolean Array

Intuition Since the input consists only of lowercase English letters, we can use a fixed-size boolean array of length 26 to track seen characters more efficiently than a Hash Set.

Steps

• Create a boolean array of size 26 initialized to false.
• Iterate through the string. For each character, calculate its index (0-25).
• If the character hasn’t been seen, mark it as seen and increment a counter.
• Return the counter.

class Solution:
    def minimizedStringLength(self, s: str) -> int:
        seen = [0] * 26
        for c in s:
            seen[ord(c) - 97] = 1
        return sum(seen)

Complexity

• Time: O(N)
• Space: O(1)
• Notes: Slightly faster than Hash Set due to lower overhead.

Bit Manipulation

Intuition We can use a single integer as a bitmask to track the 26 possible letters. Each bit in the integer corresponds to a letter in the alphabet.

Steps

• Initialize an integer mask to 0.
• Iterate through the string. For each character, calculate the bit position (0-25).
• Use the bitwise OR operator to set the corresponding bit in the mask.
• Finally, count the number of set bits (1s) in the mask.

class Solution:
    def minimizedStringLength(self, s: str) -> int:
        mask = 0
        for c in s:
            mask |= 1 << (ord(c) - 97)
        return bin(mask).count('1')

Complexity

• Time: O(N)
• Space: O(1)
• Notes: Extremely space-efficient, uses bitwise operations for speed.