Minimize String Length

Problem Description

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.

Key Insights

• Characters that appear multiple times can be minimized by removing duplicates.
• The operations allow for targeted removal of characters based on their nearest occurrences.
• The final string length can be determined by the unique characters present in the string.

Space and Time Complexity

Time Complexity: O(n) - where n is the length of the string, as we might need to iterate through the string to identify unique characters. Space Complexity: O(1) - since we only need a fixed amount of space to store the counts of characters (26 lowercase letters).

Solution

To solve the problem, we can utilize a Hash Set (or a set data structure) to keep track of unique characters in the string. As we iterate through the string, we add each character to the set. The size of the set at the end will give us the minimized string length, as it inherently represents the unique characters left after all possible operations.

Code Solutions