Skip to content

2716. Minimize String Length

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.

 

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

Solutions

Solution 1: Hash Table

Thinking

An operation deletes occurrences of a character on both sides of a chosen copy. Simulating the deletions would rescan the string, yet a character never disappears entirely.

Each distinct character survives exactly once, so the answer is the number of unique characters — the size of a set built from \(s\).

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 \(\textit{s}\). The space complexity is \(O(|\Sigma|)\), where \(\Sigma\) is the character set. In this case, it's lowercase English letters, so \(|\Sigma|=26\).

1
2
3
class Solution:
    def minimizedStringLength(self, s: str) -> int:
        return len(set(s))

1
2
3
4
5
6
7
8
9
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();
    }
}

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

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

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

1
2
3
4
5
6
7
8
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
    }
}

1
2
3
4
5
public class Solution {
    public int MinimizedStringLength(string s) {
        return new HashSet<char>(s).Count;
    }
}

Comments