Skip to main content
Talentd

Minimize String Length - Solution & Explanation

EasyHash TableString15 min readAsked at: Google, Bloomberg
Practice this problem

Problem Statement

Given a string s, you have two types of operation:

  1. Choose an index 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).
  2. Choose an index 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:

  1. Operation 2: we choose 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.
  2. Operation 1: we choose 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:

  1. Operation 1: we choose 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:

  1. Operation 1: we choose 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.
  2. Operation 2: we choose 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.
  3. Operation 2: we choose 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.
  4. Operation 1: we choose 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 <= 100
  • s contains only lowercase English letters

Approach Overview

Problem 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.

Approach 1: Approach 1: Greedy with Two Pointers

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 2: Approach 2: HashMap Approach

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 3: 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.

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.

Code

PythonJavaC++GoTypeScriptRustC#

Python

Java

C++

Go

TypeScript

Rust

C#

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Greedy with Two Pointers

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.

Approach 2: HashMap Approach

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.

Hash Table—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Greedy with Two PointersO(n)O(1)When characters come from a fixed alphabet and you want a constant-space solution.
HashMap / Hash SetO(n)O(k)General case. Most readable and commonly used in interviews.

Video Solution

LeetCode 2716. Minimize String Length - Interview Prep Ep 142 • Fisher Coder • 1,766 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Minimize String Length easy or hard?
Minimize String Length is classified as an Easy problem on LeetCode. The main challenge is recognizing that duplicate characters can always be paired and removed, reducing the task to counting distinct characters.
Minimize String Length Python/Java solution
In Python, you can compute the answer using len(set(s)). In Java, use a HashSet<Character> and add each character while iterating through the string. The final set size represents the minimized string length.
How to solve Minimize String Length in O(n)?
Traverse the string once and insert each character into a hash set. Because sets only store unique elements, duplicates are effectively ignored. The size of the set at the end equals the minimum possible string length after removing pairs.
What is the best approach for Minimize String Length?
The most practical approach uses a hash set to track unique characters. Each duplicate character can be paired with another identical character and removed, leaving at most one occurrence. Counting the number of distinct characters gives the minimized length. This runs in O(n) time with O(k) space where k is the number of unique characters.
Is Minimize String Length asked at Google/Amazon/Meta?
This problem represents a common interview pattern involving hash tables and string processing. Variations of duplicate removal and frequency counting frequently appear in coding interviews at large tech companies such as Amazon, Google, and Meta.
What data structure is used in Minimize String Length?
A hash table or hash set is typically used. It allows constant-time insertion and membership checks while tracking unique characters. This makes it ideal for counting distinct characters in a string efficiently.
What is the time complexity of Minimize String Length?
The optimal solution runs in O(n) time because the algorithm scans the string once. Each character is inserted or checked in a hash set with average O(1) complexity. Space complexity is O(k), where k represents the number of distinct characters in the string.

Ready to solve this problem?

Practice Minimize String Length with our built-in code editor and test cases.

Practice on FleetCode
Previous

Remove All Adjacent Duplicates In String

Next

Remove All Adjacent Duplicates in String II