2716. Minimize String Length - Solution & Explanation

Q: 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.

Q: Minimize String Length Python/Java solution

In Python, you can compute the answer using len(set(s)). In Java, use a HashSet and add each character while iterating through the string. The final set size represents the minimized string length.

The problem

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

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).
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:

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

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:

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

Python

def minimize_string_length(s):
    s_list = list(s)
    i = 0
    while i < len(s_list):
        j = i + 1
        while j < len(s_list):
            if s_list[i] == s_list[j]:
                s_list.pop(j)
            else:
                j += 1
        i += 1
    return len(s_list)

s = "aaabc"
print("Minimized length:", minimize_string_length(s))

Java

class Solution {
    public int minimizeStringLength(String s) {
        StringBuilder sb = new StringBuilder(s);
        int length = sb.length();
        for (int i = 0; i < length; i++) {
            for (int j = i + 1; j < length; j++) {
                if (sb.charAt(i) == sb.charAt(j)) {
                    sb.deleteCharAt(j);
                    length--;
                    j--;
                }
            }
        }
        return sb.length();
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        String s = "aaabc";
        System.out.println("Minimized length: " + solution.minimizeStringLength(s));
    }
}

C++

#include <iostream>
#include <string>

int minimizeStringLength(std::string s) {
    int i = 0;
    while (i < s.size()) {
        int j = i + 1;
        while (j < s.size()) {
            if (s[i] == s[j]) {
                s.erase(s.begin() + j);
            } else {
                j++;
            }
        }
        i++;
    }
    return s.size();
}

int main() {
    std::string s = "aaabc";
    std::cout << "Minimized length: " << minimizeStringLength(s) << std::endl;
    return 0;
}

JavaScript

function minimizeStringLength(s) {
    let sArray = s.split('');
    for (let i = 0; i < sArray.length; i++) {
        for (let j = i + 1; j < sArray.length; j++) {
            if (sArray[i] === sArray[j]) {
                sArray.splice(j, 1);
                j--;
            }
        }
    }
    return sArray.length;
}

const s = "aaabc";
console.log("Minimized length:", minimizeStringLength(s));

#include <stdio.h>
#include <string.h>

int minimizeStringLength(char *s) {
    int length = strlen(s);
    int i = 0, j;

    while (i < length) {
        j = i + 1;
        while (j < length) {
            if (s[i] == s[j]) {
                memmove(&s[j], &s[j + 1], length - j);
                length--;
            } else {
                j++;
            }
        }
        i++;
    }
    return length;
}

int main() {
    char s[] = "aaabc";
    printf("Minimized length: %d\n", minimizeStringLength(s));
    return 0;
}

using System;
using System.Text;

class Solution {
    public int MinimizeStringLength(string s) {
        StringBuilder sb = new StringBuilder(s);
        int length = sb.Length;
        for (int i = 0; i < length; i++) {
            for (int j = i + 1; j < length; j++) {
                if (sb[i] == sb[j]) {
                    sb.Remove(j, 1);
                    length--;
                    j--;
                }
            }
        }
        return sb.Length;
    }

    static void Main(string[] args) {
        Solution solution = new Solution();
        string s = "aaabc";
        Console.WriteLine("Minimized length: " + solution.MinimizeStringLength(s));
    }
}

This Python solution converts the string into a list to allow for mutability. The outer and inner loops locate duplicates, removing the duplicates when found using the pop method.

Complexity

Time Complexity: O(n^2), because of the double nested list iteration.
Space Complexity: O(n), since we're using a list that could potentially expand similar to the input size.

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.

Python

def minimize_string_length(s):
    seen = set()
    result = []

    for char in s:
        if char not in seen:
            result.append(char)
            seen.add(char)

    return len(result)

s = "aaabc"
print("Minimized length:", minimize_string_length(s))

Java

import java.util.HashSet;

class Solution {
    public int minimizeStringLength(String s) {
        HashSet<Character> set = new HashSet<>();
        StringBuilder result = new StringBuilder();

        for (char c : s.toCharArray()) {
            if (!set.contains(c)) {
                result.append(c);
                set.add(c);
            }
        }
        return result.length();
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        String s = "aaabc";
        System.out.println("Minimized length: " + solution.minimizeStringLength(s));
    }
}

C++

#include <iostream>
#include <unordered_map>
#include <string>

int minimizeStringLength(std::string s) {
    std::unordered_map<char, bool> seen;
    std::string result;
    
    for (char c : s) {
        if (!seen[c]) {
            result += c;
            seen[c] = true;
        }
    }
    return result.size();
}

int main() {
    std::string s = "aaabc";
    std::cout << "Minimized length: " << minimizeStringLength(s) << std::endl;
    return 0;
}

JavaScript

function minimizeStringLength(s) {
    const seen = new Set();
    const result = [];

    for (let char of s) {
        if (!seen.has(char)) {
            result.push(char);
            seen.add(char);
        }
    }
    return result.length;
}

const s = "aaabc";
console.log("Minimized length:", minimizeStringLength(s));

#include <stdio.h>
#include <string.h>

#define CHAR_RANGE 256

int minimizeStringLength(char *s) {
    int hash[CHAR_RANGE] = {0};
    int length = strlen(s);
    char result[length];
    int idx = 0;

    for (int i = 0; i < length; i++) {
        if (hash[(int)s[i]] == 0) {
            result[idx++] = s[i];
            hash[(int)s[i]] = 1;
        }
    }
    result[idx] = '\0';

    strcpy(s, result);
    return idx;
}

int main() {
    char s[] = "aaabc";
    printf("Minimized length: %d\n", minimizeStringLength(s));
    return 0;
}

using System;
using System.Collections.Generic;
using System.Text;

class Solution {
    public int MinimizeStringLength(string s) {
        HashSet<char> seen = new HashSet<char>();
        StringBuilder result = new StringBuilder();

        foreach (char c in s) {
            if (!seen.Contains(c)) {
                result.Append(c);
                seen.Add(c);
            }
        }
        return result.Length;
    }

    static void Main(string[] args) {
        Solution solution = new Solution();
        string s = "aaabc";
        Console.WriteLine("Minimized length: " + solution.MinimizeStringLength(s));
    }
}

This Python solution utilizes a set to track previously encountered characters. Characters not found in the set are added to a result list, ensuring no duplicates appear in the final output.

Complexity

Time Complexity: O(n), since we iterate through the string once with set operations taking constant time.
Space Complexity: O(k), limited by the number of distinct characters encountered.

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.

TypeScript

function minimizedStringLength(s: string): number {
    return new Set(s.split('')).size;
}

func minimizedStringLength(s string) int {
	ss := map[rune]struct{}{}
	for _, c := range s {
		ss[c] = struct{}{}
	}
	return len(ss)
}

Rust

use std::collections::HashSet;

impl Solution {
    pub fn minimized_string_length(s: String) -> i32 {
        let ss: HashSet<char> = s.chars().collect();
        ss.len() as i32
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Approach 1: Greedy with Two Pointers	Time Complexity: O(n^2), because of the double nested list iteration. Space Complexity: O(n), since we're using a list that could potentially expand similar to the input size.
Approach 2: HashMap Approach	Time Complexity: O(n), since we iterate through the string once with set operations taking constant time. Space Complexity: O(k), limited by the number of distinct characters encountered.
Hash Table	–

Complexity analysis

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.

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.

Minimize String Length solution and explanation

The problem

Approach overview

Approach 1: Approach 1: Greedy with Two Pointers

Approach 2: Approach 2: HashMap Approach

Approach 3: Hash Table

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Minimize String Length solution and explanation

The problem

Approach overview

Approach 1: Approach 1: Greedy with Two Pointers

Approach 2: Approach 2: HashMap Approach

Approach 3: Hash Table

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems