2716. Minimize String Length

EasyHash TableString
Leetcode Link

Problem Description

In this problem, we are given a 0-indexed string s. The operation we can perform on this string is to delete the closest occurrences of a character c to the left and right of index i, where c is the character at index i. We can perform this operation any number of times with the goal to minimize the length of string s as much as possible. The task is to return the length of the string after performing the operation optimally to minimize the string length.

Intuition

To solve this problem, we need to find a way to reduce the string length as much as possible by deleting characters. One might initially think that keeping track of the occurrences and their positions is required. However, on careful observation, we can note that in the best case scenario, each unique character can completely remove its closest occurrence to the left and right for every other duplicate character.

If we consider an example: Given a string s = "abcddcba", we can see this:

  • For 'a', the closest 'a' to the left of the second 'a' is the first 'a', and similarly for the closest to the right.
  • The same argument applies to 'b', 'c', and 'd'.

The optimal removal would remove all characters except for one instance of each unique character. Thus, our problem simplifies to counting the number of unique characters in the string since in the minimized string, every character that has duplicates would have only one instance left.

Therefore, the solution approach to finding the length of the minimized string is to simply return the count of unique characters in the string, which can be found using the set() function in Python that returns all unique elements, and then using the len() function to count these unique elements.

Solution Approach

The implementation of the solution is straightforward because of the simplicity of the problem once we understand the pattern. We utilize the fact that for any character that has duplicates in the string, all its occurrences except one will eventually be removed. By following this logic, we can infer that the solution does not require complex algorithms or data structures.

The approach consists of two steps:

  1. Convert the string into a set of characters, which eliminates any duplicate occurrences of characters. We use the set() constructor in Python, which takes an iterable, such as a string, and returns a new set object with distinct elements.
  2. Calculate the length of this set, which gives us the number of unique characters in the original string. To get the count, we use the len() function which returns the number of items in a container.

By employing these built-in functions, set and len, we efficiently solve the problem without the need for any additional data structure or algorithm. The pattern recognized here is essentially a unique element count problem which often leads to the use of sets for their property of containing non-duplicate elements.

The Python code is as follows:

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

In the code, s is the input string. We pass s to the set() function which removes all duplicate characters. Then, we pass the resulting set to the len() function to get the total count of unique characters. This count represents the length of the minimized string, according to the problem statement.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8
1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12
1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

Example Walkthrough

Let's illustrate the solution approach with a small example. Consider the string s = "abacabad". According to the problem, we want to delete occurrences of characters that are closest to the left and right of any instance of that character. Following the solution approach, here's a step-by-step walkthrough:

  1. Convert the string s into a set of characters to get the unique characters. For our example, converting s to a set would look like this:
1unique_chars = set("abacabad")
2print(unique_chars)  # Output will be {'a', 'b', 'c', 'd'}

After converting to a set, we have {'a', 'b', 'c', 'd'}, which represents the unique characters in the string.

  1. Calculate the length of this set to find out how many unique characters we have:
1length = len(unique_chars)
2print(length)  # Output will be 4

The length of the unique character set is 4, which means there are four unique characters in the string s.

Following the intuition of the problem, these four unique characters would be the characters that remain after optimally performing the given operation (i.e., deleting the closest occurrences of a character to the left and right of index i). Therefore, the length of the string after performing the operations is the same as the number of unique characters in the original string, which is 4 in this case.

Thus, using the set() function in Python, we eliminated all the duplicates, and by using the len() function, we efficiently found the minimized string length. This example perfectly illustrates how the solution approach leads to an optimal and simplistic answer.

Solution Implementation

1class Solution:
2    def minimizedStringLength(self, s: str) -> int:
3        # Create a set from the string 's' to eliminate any duplicate characters.
4        unique_characters = set(s)
5
6        # The minimized string length is equal to the number of unique characters.
7        minimized_length = len(unique_characters)
8
9        # Return the length of the minimized string.
10        return minimized_length
11
1class Solution {
2    // Function to compute the minimized string length based on unique characters
3    public int minimizedStringLength(String inputString) {
4        // Create a HashSet to store unique characters
5        Set<Character> uniqueCharacters = new HashSet<>();
6      
7        // Iterate through all characters in the input string
8        for (int i = 0; i < inputString.length(); ++i) {
9            // Add each character to the Set, duplicates are automatically ignored
10            uniqueCharacters.add(inputString.charAt(i));
11        }
12      
13        // The size of the Set represents the number of unique characters
14        // Return this size as the minimized string length
15        return uniqueCharacters.size();
16    }
17}
18
1#include <unordered_set> // Include necessary header for unordered_set
2#include <string> // Include necessary header for string
3
4class Solution {
5public:
6    // Function to calculate the minimized string length
7    int minimizedStringLength(std::string s) {
8        // Create an unordered_set to store unique characters
9        std::unordered_set<char> unique_characters(s.begin(), s.end());
10
11        // The size of the set gives us the count of unique characters
12        return unique_characters.size();
13    }
14};
15
1// This function calculates the minimized length of a string 
2// by removing all duplicate characters.
3// @param {string} inputString - The string to be processed.
4// @returns {number} The count of unique characters in the input string.
5
6function minimizedStringLength(inputString: string): number {
7    // Split the input string into its individual characters,
8    // convert it into a Set to remove duplicates,
9    // and then return the size of the Set.
10    return new Set(inputString.split('')).size;
11}
12

Time and Space Complexity

Time Complexity

The time complexity of the minimizedStringLength function is O(n), where n is the length of the string s. This is because the function iterates through each character in the string exactly once to create a set of unique characters.

Space Complexity

The space complexity of the function is O(k), where k is the number of unique characters in the string s. In the worst case, if all characters are unique, k would be equal to n, resulting in a space complexity of O(n). However, considering the input is a string with a fixed character set (e.g., ASCII characters), k can also be considered a constant, and hence the space complexity can be O(1) in the context of a fixed character set.

Learn more about how to find time and space complexity quickly using problem constraints.


Fast Track Your Learning with Our Quick Skills Quiz:

What are the two properties the problem needs to have for dynamic programming to be applicable? (Select 2)


Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


🪄