3223. Minimum Length of String After Operations

MediumHash TableStringCounting

Problem Description

You are given a string s. You can perform the following process on s any number of times:

Choose an index i in the string such that there is at least one character to the left of index i that is equal to s[i], and at least one character to the right that is also equal to s[i].
Delete the closest character to the left of index i that is equal to s[i].
Delete the closest character to the right of index i that is equal to s[i].

Return the minimum length of the final string s that you can achieve.

Intuition

The process essentially revolves around reducing the occurrence of identical characters from both sides until no more deletions are possible. The minimum possible length of the string can be calculated based on the frequency of each character.

The key observation here is that for characters appearing an odd number of times, one will always remain in the string, since you can remove pairs symmetrically from the middle until one remains unmatched. For those that appear an even number of times, at least two of them will remain if they start as pairs.

To achieve this, we count the occurrences of each character in the string. For each character frequency, if the character appears an odd number of times, it will contribute 1 to the final count. If it appears an even number, it will contribute 2 to the final minimum length. The summation of these remainder counts for all characters will yield the final length.

Solution Approach

The solution employs a straightforward counting strategy to determine the minimum possible length of the string after applying the removal process described. Here's a detailed walk through the implementation:

Counting Occurrences:
- We begin by counting the occurrences of each character in the string s. This can be efficiently done using a data structure like Counter from Python's collections module, which allows us to quickly tally the frequency of each character.
Calculate Minimum Length:
- Once we have the counts, we iterate through these counts to determine the contribution of each character to the final string length.
- For each character count, if the count is odd, it contributes 1 to the final length because we can't completely remove matching pairs; one character will always be left over.
- If the count is even, it contributes 2 because all characters form pairs that can be symmetrically reduced down to two remaining characters (as explained earlier).

Implementation:

In code, this approach can be written concisely as:

from collections import Counter

class Solution:
    def minimumLength(self, s: str) -> int:
        cnt = Counter(s)
        return sum(1 if x & 1 else 2 for x in cnt.values())

In this implementation:

Counter(s) provides a dictionary-like object that holds the frequency of each character.
The function then iterates over the values of this counter. For each count x, 1 if x & 1 else 2 checks if x is odd or even, contributing either 1 or 2 accordingly to the total sum.
The sum function aggregates the results, giving the minimum length possible after the described process.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Consider the string s = "abbaac". Let's apply the solution approach to determine the minimum length of the final string:

Counting Occurrences:
- First, we count the number of occurrences of each character in the string. For s = "abbaac", we have:
  - 'a': 3 occurrences
  - 'b': 2 occurrences
  - 'c': 1 occurrence
Calculate Minimum Length:
- For each character, we evaluate its count:
  - 'a' appears 3 times (odd), so it contributes 1 to the final length.
  - 'b' appears 2 times (even), so it contributes 2 to the final length.
  - 'c' appears 1 time (odd), so it contributes 1 to the final length.
- Summing these contributions: 1 (for 'a') + 2 (for 'b') + 1 (for 'c') = 4.

The minimum length of the final string s that can be achieved after applying the process is therefore 4.

Solution Implementation

1from collections import Counter
2
3class Solution:
4    def minimumLength(self, s: str) -> int:
5        # Create a counter to count occurrences of each character in the string
6        cnt = Counter(s)
7        # For each character count, return 1 if count is odd, 2 if even; calculate the total sum
8        return sum(1 if count % 2 == 1 else 2 for count in cnt.values())
9

1class Solution {
2    public int minimumLength(String s) {
3        // Array to count occurrences of each character (assuming lowercase a-z)
4        int[] characterCount = new int[26];
5
6        // Count each character's frequency in the string
7        for (int i = 0; i < s.length(); ++i) {
8            characterCount[s.charAt(i) - 'a']++;
9        }
10
11        int result = 0;
12
13        // Calculate minimum length required
14        for (int count : characterCount) {
15            // Only consider characters that appear in the string
16            if (count > 0) {
17                // If character appears an odd number of times, add 1, if even add 2
18                result += (count % 2 == 1) ? 1 : 2;
19            }
20        }
21
22        return result;
23    }
24}
25

1class Solution {
2public:
3    int minimumLength(string s) {
4        // Array to count the frequency of each character in the string
5        int characterCount[26] = {};
6      
7        // Iterate over each character in the string and increment its count
8        for (char& character : s) {
9            ++characterCount[character - 'a'];
10        }
11      
12        int minimumLength = 0;
13      
14        // Iterate over the count of each character
15        for (int count : characterCount) {
16            // If the character appears in the string
17            if (count > 0) {
18                // Add 1 if count is odd; add 2 if even
19                minimumLength += (count % 2 == 1) ? 1 : 2;
20            }
21        }
22      
23        // Return the calculated minimum length
24        return minimumLength;
25    }
26};
27

1function minimumLength(s: string): number {
2    // Create a map to count occurrences of each character
3    const characterCountMap = new Map<string, number>();
4  
5    // Populate the map with character counts
6    for (const char of s) {
7        characterCountMap.set(char, (characterCountMap.get(char) || 0) + 1);
8    }
9  
10    // Initialize the result variable to store the minimum length
11    let result = 0;
12  
13    // Calculate the minimum length based on character occurrences
14    for (const count of characterCountMap.values()) {
15        // Add 1 if the count is odd, otherwise add 2
16        result += (count & 1) ? 1 : 2;
17    }
18  
19    return result;
20}
21

Time and Space Complexity

The time complexity of the code is O(n), where n is the length of the string s, because each character in the string is processed in order to count occurrences. The Counter from the collections module handles this efficiently.

The space complexity is O(|Σ|), where |Σ| represents the size of the character set. Since we are dealing with lowercase English letters, |Σ| is 26, and the Counter stores frequencies for each character.

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

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

Question 1 out of 10

Which of these properties could exist for a graph but not a tree?

Contain cycles

There are multiple ways to traverse

Connected

Has no cycle

I don’t know