# Minimize String Length
**Difficulty:** EASY
[External](https://leetcode.com/problems/minimize-string-length)
Canonical: https://scaleengineer.com/dsa/problems/minimize-string-length
**Data structures:** Hash Table, String
---
## Problem
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

# Approaches
## Sorting-based Approach
This approach is based on the realization that the operations allow us to remove any duplicate characters, ultimately leaving only one of each unique character. The problem thus simplifies to counting the number of unique characters in the string. A straightforward way to count unique elements is to sort the collection first, which groups identical elements together, making them easy to count.
**Time:** O(N log N), where N is the length of the string. The dominant part of this algorithm is the sorting step, which typically has a time complexity of O(N log N). · **Space:** O(N), where N is the length of the string. This is because in Java, strings are immutable, so we need to create a new character array of size N to perform the sort.
**Pros:** The logic is relatively simple and easy to follow.; It correctly determines the number of unique characters, which is the solution to the problem.
**Cons:** This approach is less efficient than linear time solutions due to the sorting step.; It requires extra space to hold the character array, as strings are immutable in Java.
### Explanation
The core idea is that the complex deletion operations described in the problem statement effectively allow for the removal of any duplicate character. If a character appears more than once, we can always find two occurrences and eliminate one. This can be repeated until only one instance of that character remains. This logic applies to all characters in the string. Therefore, the minimum possible length of the string is simply the number of unique characters present in the original string.

To implement this, we first convert the string to a character array. Then, we sort this array using a standard sorting algorithm. After sorting, all occurrences of the same character will be adjacent to each other. We can then iterate through the sorted array once to count the unique characters. We start a counter at 1 (assuming the string is not empty) and increment it every time we find a character that is different from the one immediately preceding it.

For example, if `s = "baadccab"`, the sorted character array would be `['a', 'a', 'a', 'b', 'b', 'c', 'c', 'd']`. By scanning this array, we can count the unique characters: 'a', 'b', 'c', and 'd', for a total of 4.

```java
import java.util.Arrays;

class Solution {
    public int minimizedStringLength(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        char[] chars = s.toCharArray();
        Arrays.sort(chars);
        
        int uniqueCount = 1;
        for (int i = 1; i < chars.length; i++) {
            if (chars[i] != chars[i - 1]) {
                uniqueCount++;
            }
        }
        return uniqueCount;
    }
}
```
### Algorithm
- Convert the input string `s` into a character array `chars`.
- Sort the `chars` array. This will group all identical characters together.
- If the string is empty, the result is 0.
- Initialize a counter `uniqueCount` to 1, accounting for the first character in the sorted array.
- Iterate through the sorted array from the second element (`i = 1`).
- In each iteration, compare the current character `chars[i]` with the previous one `chars[i-1]`.
- If they are different, it means we have encountered a new unique character, so we increment `uniqueCount`.
- After the loop finishes, `uniqueCount` will hold the total number of distinct characters.

## Optimal Approach using Hash Set or Frequency Array
The most efficient approach recognizes that the problem simplifies to counting unique characters. Instead of sorting, we can use a data structure that provides constant-time average insertion and lookup to keep track of the characters we have already seen. A `HashSet` is ideal for this purpose. Given the constraint that characters are only lowercase English letters, a simple boolean array can also serve as a highly efficient frequency map.
**Time:** O(N), where N is the length of the string. We perform a single pass through the string. Operations like adding to a `HashSet` or accessing an array index take constant time on average. · **Space:** O(1). The `HashSet` will store at most 26 characters, and the boolean array has a fixed size of 26. In both cases, the space used is constant and does not depend on the length of the input string.
**Pros:** Optimal time complexity of O(N).; Optimal space complexity of O(1) because the alphabet size is constant.; Very simple and concise to implement.
**Cons:** There are no significant cons for this approach as it is optimal for the given constraints.
### Explanation
This optimal approach is also based on the insight that the operations allow for the removal of all duplicate characters, reducing the problem to counting the distinct characters in the string. We can achieve this in linear time.

**Method 1: Using a HashSet**
A `HashSet` stores only unique elements. We can iterate through the input string and add each character to a `HashSet`. The set's internal logic ensures that duplicates are not stored. After iterating through the entire string, the size of the `HashSet` will give us the count of unique characters.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int minimizedStringLength(String s) {
        Set<Character> uniqueChars = new HashSet<>();
        for (char c : s.toCharArray()) {
            uniqueChars.add(c);
        }
        return uniqueChars.size();
    }
}
```

**Method 2: Using a Frequency Array**
Since the problem specifies that the string contains only lowercase English letters (a-z), we can use a simple boolean array of size 26 as a direct address table or frequency map. Each index in the array corresponds to a letter of the alphabet. We iterate through the string, and for each character, we mark its corresponding index in the array as `true`. We can also maintain a counter that increments only when we see a character for the first time. This avoids a second pass over the frequency array.

```java
class Solution {
    public int minimizedStringLength(String s) {
        boolean[] seen = new boolean[26];
        int uniqueCount = 0;
        for (char c : s.toCharArray()) {
            if (!seen[c - 'a']) {
                seen[c - 'a'] = true;
                uniqueCount++;
            }
        }
        return uniqueCount;
    }
}
```
Both methods are highly efficient and perfectly suited for this problem.
### Algorithm
- **Using a HashSet:**
  - Initialize an empty `HashSet<Character>` named `uniqueChars`.
  - Iterate through each character `c` of the input string `s`.
  - For each character, add it to the `uniqueChars` set. The set will automatically handle duplicates; adding an existing element has no effect.
  - After the loop, the size of the `uniqueChars` set is the number of distinct characters. Return this size.

- **Using a Frequency Array:**
  - Since the input consists of only lowercase English letters, we can use a boolean array `seen` of size 26.
  - Initialize the `seen` array with all `false` values.
  - Initialize a counter `uniqueCount` to 0.
  - Iterate through each character `c` of the input string `s`.
  - For each character, calculate its corresponding index in the array (`index = c - 'a'`).
  - If `seen[index]` is `false`, it means this is the first time we've encountered this character. Set `seen[index]` to `true` and increment `uniqueCount`.
  - After the loop, return `uniqueCount`.

# Solutions
### CSharp

```csharp
public class Solution { public int MinimizedStringLength ( string s ) { return new HashSet < char >( s ). Count ; } }
```

### Java

```java
class Solution {
public
  int minimizedStringLength(String s) {
    Set<Character> ss = new HashSet<>();
    for (int i = 0; i < s.length(); ++i) {
      ss.add(s.charAt(i));
    }
    return ss.size();
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minimizedStringLength(string s) {
    unordered_set<char> ss(s.begin(), s.end());
    return ss.size();
  }
};

```

### Python

```python
class Solution:
    def minimizedStringLength(self, s: str) -> int: return len(set(s))

```