LeetCode 3223 | Minimum Length of String After Operations - Solution Explained

LeetCode Problem 3223 asks us to perform a series of operations on a given string to minimize its length. The operation allows us to choose an index i in the string such that there are at least two characters in the string equal to s[i]: one to the left and one to the right. Once we choose such an index, we delete the closest occurrence of the same character to the left and to the right of index i. The goal is to return the minimum length of the string that can be achieved after performing the operation any number of times.

Let's walk through an example to better understand the problem:

Example 1:

Input: s = "abaacbcbb"
Output: 5

Explanation:

1. Initially, the string is "abaacbcbb".
2. We can pick index 2 (character 'a') because it has a matching character on both sides ('a' at index 0 and 'a' at index 3).
   • We delete the characters at indices 0 and 3, so the string becomes "bacbcbb".
3. We pick index 3 (character 'b'), and the closest matching characters are 'b' at index 0 and 'b' at index 5.
   • We delete the characters at indices 0 and 5, leaving us with "acbcb".
4. The string is now minimized, and its length is 5.

Example 2:

Input: s = "aa"
Output: 2

Explanation: We can't perform any operation because there are no matching characters on both sides of any index. Thus, the length of the string remains the same, and the output is 2.

Problem can be tricky because we need to choose indices carefully and optimize the number of deletions to minimize the length of the string. The challenge lies in ensuring that we don’t waste operations, which can happen if we don’t pick indices with valid matching characters on both sides.

Approach to Solve the Problem:

The key observation here is that the solution revolves around the frequency of characters and whether those frequencies are even or odd. Here's how we can break it down:

1. Count Character Frequencies: We start by counting the frequency of each character in the string. This helps us understand how many characters are available to perform operations on.
2. Even vs. Odd Frequencies: For each character:
   • If the frequency is even, we can always delete two characters (one from the left and one from the right).
   • If the frequency is odd, we can delete one character, leaving one character behind.
3. Summing Up: We add the corresponding results for each character and return the minimized length.

Solution Code:

class Solution
{
public:
    int minimumLength(string s)
    {
        vector<int> freq(26, 0);
        // Step 1: Count the frequency of each character in the string
        for (int i = 0; i < s.length(); i++)
        {
            freq[s[i] - 'a']++;
        }
        int count = 0;
        // Step 2: Calculate the result based on frequency
        for (int i = 0; i < 26; i++)
        {
            if (freq[i] > 0)
            {
                if (freq[i] % 2 == 0)
                    count += 2; // For even frequencies, we can remove two characters
                else
                    count += 1; // For odd frequencies, we can remove one character
            }
        }
        return count; // Return the minimized length of the string
    }
};

Explanation of the Code:

1. Counting Frequencies:

   • We use a vector freq of size 26 (since there are 26 lowercase English letters) to store the frequency of each character in the string.
   • The expression s[i] - 'a' helps us map each character to its corresponding index (e.g., 'a' -> 0, 'b' -> 1, ..., 'z' -> 25).

2. Processing Frequencies:

   • We iterate through the frequency vector. If a character has a frequency greater than 0, we check if it's even or odd:
     • For even frequencies, we can delete two characters (hence, we add 2 to the result).
     • For odd frequencies, we can only delete one character (hence, we add 1 to the result).

3. Return the Result: The final result, count, represents the minimized length of the string after performing all possible operations.

Time Complexity:

• Counting Frequencies: This takes O(n), where n is the length of the string.
• Processing Frequencies: This takes O(1) since we are iterating over a fixed-size array (26 characters).
• Overall Time Complexity: O(n), where n is the length of the string.

Space Complexity:

• We are using a vector of size 26 to store character frequencies, so the space complexity is O(1) since the size of the frequency array is constant.

The problem may initially seem tricky, but with the right approach focusing on character frequencies, we can achieve an optimal solution in linear time. This solution is efficient enough to handle the upper constraint where the length of the string can be as large as 2 * 10^5.

• The solution revolves around understanding character frequencies and their parity (even or odd).
• A frequency-based approach provides an elegant solution with O(n) time complexity.
• This problem teaches how breaking down character operations can lead to efficient string manipulations.