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.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


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

1
2
3
4
5
6
7
8
9


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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


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

Solution

Method 1 – Hash Set

Intuition

Each operation allows you to remove duplicate occurrences of a character, so the minimum possible length is the number of unique characters in the string.

Approach

  1. Use a set to collect all unique characters in the string.
  2. The answer is the size of the set.

Code

1
2
3
4
5
6
7

class Solution {
public:
    int minimizedStringLength(string s) {
        unordered_set<char> st(s.begin(), s.end());
        return st.size();
    }
};
1
2
3
4
5
6
7

func minimizedStringLength(s string) int {
    st := make(map[rune]struct{})
    for _, c := range s {
        st[c] = struct{}{}
    }
    return len(st)
}
1
2
3
4
5
6
7

class Solution {
    public int minimizedStringLength(String s) {
        Set<Character> st = new HashSet<>();
        for (char c : s.toCharArray()) st.add(c);
        return st.size();
    }
}
1
2
3
4
5

class Solution {
    fun minimizedStringLength(s: String): Int {
        return s.toSet().size
    }
}
1
2

def minimized_string_length(s: str) -> int:
    return len(set(s))
1
2
3
4
5
6
7

impl Solution {
    pub fn minimized_string_length(s: String) -> i32 {
        use std::collections::HashSet;
        let st: HashSet<char> = s.chars().collect();
        st.len() as i32
    }
}
1
2
3
4
5

class Solution {
    minimizedStringLength(s: string): number {
        return new Set(s).size;
    }
}

Complexity

  • ⏰ Time complexity: O(n)
    • Each character is processed once.
  • 🧺 Space complexity: O(1)
    • At most 26 unique lowercase letters stored in the set.