Given a string s, you have two types of operation:
i in the string, and let c be the character in position i. Delete the closest occurrence of c to the left of i (if exists).i in the string, and let c be the character in position i. Delete the closest occurrence of c to the right of i (if exists).Your task is to minimize the length of s by performing the above operations zero or more times.
Return an integer denoting the length of the minimized string.
Example 1:
Input: s = "aaabc"
Output: 3
Explanation:
i = 1 so c is 'a', then we remove s[2] as it is closest 'a' character to the right of s[1].s becomes "aabc" after this.i = 1 so c is 'a', then we remove s[0] as it is closest 'a' character to the left of s[1].s becomes "abc" after this.Example 2:
Input: s = "cbbd"
Output: 3
Explanation:
i = 2 so c is 'b', then we remove s[1] as it is closest 'b' character to the left of s[1].s becomes "cbd" after this.Example 3:
Input: s = "baadccab"
Output: 4
Explanation:
i = 6 so c is 'a', then we remove s[2] as it is closest 'a' character to the left of s[6].s becomes "badccab" after this.i = 0 so c is 'b', then we remove s[6] as it is closest 'b' character to the right of s[0].s becomes "badcca" fter this.i = 3 so c is 'c', then we remove s[4] as it is closest 'c' character to the right of s[3].s becomes "badca" after this.i = 4 so c is 'a', then we remove s[1] as it is closest 'a' character to the left of s[4].s becomes "bdca" after this.
Constraints:
1 <= s.length <= 100s contains only lowercase English lettersProblem Overview: You are given a string s. You may repeatedly remove two equal characters from the string. After each removal the remaining characters join together. The task is to return the minimum possible length after performing any number of such operations.
The key observation: duplicates can always be paired and removed. For every character that appears multiple times, you can repeatedly remove pairs until at most one instance remains. The final string therefore contains only one copy of each character that originally appeared.
Approach 1: Greedy with Two Pointers (O(n) time, O(1) space)
This greedy idea relies on the fact that every duplicate character can eventually be paired and removed. You iterate through the string and track which characters have already appeared. Conceptually, you "pair off" duplicates as soon as you encounter them. Two-pointer reasoning helps visualize the process: duplicates from earlier and later positions can always be matched and removed. In practice, you maintain a small fixed-size structure (like a boolean array for 26 lowercase letters) and mark characters as seen. The final minimized length equals the count of unique characters encountered. Time complexity is O(n) since each character is processed once, and space complexity is O(1) because the alphabet size is constant.
Approach 2: HashMap / Hash Set (O(n) time, O(k) space)
A more explicit approach uses a hash table or set. Iterate through the string and insert each character into a set. Since sets store unique values, duplicates are automatically collapsed. The size of the set represents the minimal possible string length after removing pairs. This approach works because every extra occurrence of a character can be paired with another identical character and deleted. The algorithm runs in O(n) time due to a single pass through the string with constant-time hash operations, and O(k) space where k is the number of distinct characters.
The solution mainly uses ideas from string processing and hash tables. The core trick is recognizing that the operation does not depend on positions of characters—only on whether duplicates exist.
Recommended for interviews: The hash set approach is the clearest and most commonly expected solution. It demonstrates quick pattern recognition and uses standard O(1) hash lookups. The greedy interpretation helps explain why duplicates can always be removed, while the hash-based implementation shows practical coding efficiency.
This approach uses a 'two-pointer' technique to remove duplicates efficiently by checking and erasing characters from the left or the right based on the proximity of duplicates. The idea is to traverse the string and when a duplicate is found, remove the closest duplicate to quickly reduce the string length.
This C solution uses a manual memory move with memmove to remove duplicates. It traverses the string using two pointers i and j. When it finds two identical characters, it removes the second one by shifting all subsequent characters one position to the left.
Time Complexity: O(n^2), where n is the string length, due to the nested loop.
Space Complexity: O(1), since we operate in-place.
This alternative approach uses a hash map (or dictionary) to keep track of character positions and efficiently remove duplicates. By storing indices of each character, we can quickly find duplicates and decide whether to remove them from the left or the right.
This C implementation uses an array to simulate a hash map for character occurrences. It records each character's presence in the string and builds a result array without duplicates, effectively minimizing the string.
Time Complexity: O(n), where n is the length of the string as each character is processed once.
Space Complexity: O(1), due to fixed-size additional space.
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.
The time complexity is O(n), where n is the length of the string s. The space complexity is O(|\Sigma|), where \Sigma is the character set. In this case, it's lowercase English letters, so |\Sigma|=26.
| Approach | Complexity |
|---|---|
| Approach 1: Greedy with Two Pointers | Time Complexity: O(n^2), where n is the string length, due to the nested loop. |
| Approach 2: HashMap Approach | Time Complexity: O(n), where n is the length of the string as each character is processed once. |
| Hash Table | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy with Two Pointers | O(n) | O(1) | When characters come from a fixed alphabet and you want a constant-space solution. |
| HashMap / Hash Set | O(n) | O(k) | General case. Most readable and commonly used in interviews. |
LeetCode 2716. Minimize String Length - Interview Prep Ep 142 • Fisher Coder • 1,689 views views
Watch 9 more video solutions →Practice Minimize String Length with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor