LeetCode 2716 - Minimize String Length
The problem asks us to minimize the length of a given string s by repeatedly performing two types of deletion operations. In the first operation, we can pick a character at some index and delete the closest identical character to its left if one exists.
Difficulty: 🟢 Easy
Topics: Hash Table, String
Solution
Problem Understanding
The problem asks us to minimize the length of a given string s by repeatedly performing two types of deletion operations. In the first operation, we can pick a character at some index and delete the closest identical character to its left if one exists. In the second operation, we can pick a character and delete the closest identical character to its right if one exists. Our goal is to perform these operations any number of times so that the resulting string is as short as possible, and then return its length.
The input is a string s of length between 1 and 100, containing only lowercase English letters. The output is a single integer representing the minimal possible string length after performing the operations optimally. Key observations from the constraints are that the string length is small, and we only need to track character uniqueness because any duplicate character can be removed using the allowed operations. This guarantees that the final string can contain at most one occurrence of each distinct character, because duplicates can always be deleted. Therefore, the minimized length is equal to the number of unique characters in the string.
Important edge cases include strings with all identical characters (minimal length is 1), strings with all distinct characters (minimal length is the length itself), and empty strings (though the constraints guarantee at least one character).
Approaches
The brute-force approach would attempt all possible sequences of operations, simulating the deletion process. For each character, we could try deleting to the left or right recursively. While correct, this approach is extremely inefficient because the number of possible deletion sequences grows exponentially with the length of the string. For a string of length n, there could be up to 2^(n-1) sequences, making it infeasible even for moderate lengths.
The key insight for an optimal solution is that the operations allow us to remove any duplicate of a character, regardless of its position. This means that each distinct character will appear at most once in the minimized string. Therefore, we only need to count the number of unique characters in the string. This can be done efficiently using a hash set.
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(2^n) | O(n) | Simulate all deletion sequences; exponential and unnecessary |
| Optimal | O(n) | O(1) | Count unique characters using a set; minimal length equals number of unique characters |
Algorithm Walkthrough
- Initialize an empty set to keep track of characters encountered.
- Iterate through each character in the string
s. - For each character, add it to the set. Sets inherently ignore duplicates, so we only store unique characters.
- After iterating through the entire string, the size of the set represents the number of unique characters.
- Return the size of the set as the minimized string length.
Why it works: The operations allow removal of duplicates regardless of their positions. Hence, for any character appearing more than once, we can always remove all but one. The number of remaining characters in the minimized string is exactly the number of unique characters, which is captured by the set.
Python Solution
class Solution:
def minimizedStringLength(self, s: str) -> int:
unique_chars = set()
for char in s:
unique_chars.add(char)
return len(unique_chars)
The implementation creates a set unique_chars to store all unique characters in the string. Iterating through each character, we add it to the set. After the loop, the size of the set reflects the number of distinct characters, which is exactly the minimized length of the string.
Go Solution
func minimizedStringLength(s string) int {
uniqueChars := make(map[rune]struct{})
for _, char := range s {
uniqueChars[char] = struct{}{}
}
return len(uniqueChars)
}
In Go, we use a map with empty struct values to emulate a set. Each rune (character) from the string is inserted into the map. After processing the entire string, the number of keys in the map corresponds to the number of unique characters, which is returned.
Worked Examples
Example 1: s = "aaabc"
| Step | Action | Set State | Minimized Length |
|---|---|---|---|
| 1 | Add 'a' | {'a'} | 1 |
| 2 | Add 'a' | {'a'} | 1 |
| 3 | Add 'a' | {'a'} | 1 |
| 4 | Add 'b' | {'a','b'} | 2 |
| 5 | Add 'c' | {'a','b','c'} | 3 |
Output: 3
Example 2: s = "cbbd"
| Step | Action | Set State | Minimized Length |
|---|---|---|---|
| 1 | Add 'c' | {'c'} | 1 |
| 2 | Add 'b' | {'c','b'} | 2 |
| 3 | Add 'b' | {'c','b'} | 2 |
| 4 | Add 'd' | {'c','b','d'} | 3 |
Output: 3
Example 3: s = "baadccab"
| Step | Action | Set State | Minimized Length |
|---|---|---|---|
| 1 | Add 'b' | {'b'} | 1 |
| 2 | Add 'a' | {'a','b'} | 2 |
| 3 | Add 'a' | {'a','b'} | 2 |
| 4 | Add 'd' | {'a','b','d'} | 3 |
| 5 | Add 'c' | {'a','b','d','c'} | 4 |
| 6 | Add 'c' | {'a','b','d','c'} | 4 |
| 7 | Add 'a' | {'a','b','d','c'} | 4 |
| 8 | Add 'b' | {'a','b','d','c'} | 4 |
Output: 4
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n) | We iterate through the string once, adding each character to a set/map. |
| Space | O(1) | Maximum 26 lowercase English letters, so the set/map size is bounded by 26. |
The complexity is very efficient because the input is small and the number of distinct characters is limited.
Test Cases
# Provided examples
assert Solution().minimizedStringLength("aaabc") == 3 # multiple duplicates
assert Solution().minimizedStringLength("cbbd") == 3 # duplicate 'b'
assert Solution().minimizedStringLength("baadccab") == 4 # mixed duplicates
# Edge cases
assert Solution().minimizedStringLength("a") == 1 # single character
assert Solution().minimizedStringLength("abcdef") == 6 # all unique
assert Solution().minimizedStringLength("zzzzzz") == 1 # all identical
assert Solution().minimizedStringLength("abababab") == 2 # two alternating characters
| Test | Why |
|---|---|
| "aaabc" | Tests consecutive duplicates removal |
| "cbbd" | Tests duplicates in middle of string |
| "baadccab" | Tests mixed duplicates spread across string |
| "a" | Tests single-character string |
| "abcdef" | Tests all unique characters |
| "zzzzzz" | Tests all identical characters |
| "abababab" | Tests alternating duplicates |
Edge Cases
The first edge case is a string with all identical characters, such as "zzzz". In this case, the minimal length is 1. Our implementation handles it correctly because the set only stores one occurrence of each character.
The second edge case is a string with all unique characters, such as "abcdef". Here, no deletions are possible, and the minimal length equals the string length. The algorithm correctly returns the size of the set, which is the string length.
The third edge case is a string where characters alternate repeatedly, like "ababab". Multiple deletions could occur using the operations, but the result still only retains one 'a' and one 'b'. The set approach correctly computes the minimal length as 2.
This solution correctly handles all these edge cases with consistent logic and does not require simulating any deletions explicitly.