3223: Minimum Length of String After Operations

Problem Statement

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

1. Choose an index i where there's at least one matching character to the left and right of i
2. Delete the closest occurrence to the left of i
3. Delete the closest occurrence to the right of i

Return the minimum possible length of s after performing these operations.

Example 1

Input: s = "abaacbcbb"
Output: 5
Explanation:
1. Choose index 2 (first 'a'), remove at indices 0 and 3 → "bacbcbb"
2. Choose index 3 (first 'b'), remove at indices 0 and 5 → "acbcb"

Example 2

Input: s = "aa"
Output: 2
Explanation: No operations possible

Approach 1: Frequency Analysis (Optimal)

Count character frequencies and determine minimal length based on parity.

Algorithm Steps

1. Count frequency of each character
2. For each character:
   • If frequency is even: Can remove all but 2
   • If frequency is odd: Can remove all but 1
3. Sum remaining counts

Complexity Analysis

class Solution {
public:
    int minimumLength(string s) {
        vector<int> freq(26, 0);
        for(char c : s) freq[c-'a']++;
        
        int result = 0;
        for(int count : freq) {
            if(count == 0) continue;
            result += (count % 2 == 0) ? 2 : 1;
        }
        return result;
    }
};

class Solution {
    public int minimumLength(String s) {
        int[] freq = new int[26];
        for(char c : s.toCharArray()) freq[c-'a']++;
        
        int result = 0;
        for(int count : freq) {
            if(count == 0) continue;
            result += (count % 2 == 0) ? 2 : 1;
        }
        return result;
    }
}

class Solution:
    def minimumLength(self, s: str) -> int:
        freq = [0] * 26
        for c in s:
            freq[ord(c) - ord('a')] += 1
            
        return sum(2 if c % 2 == 0 else 1 for c in freq if c > 0)

Approach 2: Two Pointers

Alternative solution using two pointers to simulate the operations.

Algorithm Steps

1. Initialize left and right pointers
2. While characters match at both ends:
   • Move pointers inward past matching characters
   • Track remaining length
3. Return final length

Complexity Analysis

class Solution {
public:
    int minimumLength(string s) {
        int left = 0, right = s.size() - 1;
        while(left < right && s[left] == s[right]) {
            char current = s[left];
            while(left <= right && s[left] == current) left++;
            while(left <= right && s[right] == current) right--;
        }
        return right - left + 1;
    }
};

class Solution {
    public int minimumLength(String s) {
        int left = 0, right = s.length() - 1;
        while(left < right && s.charAt(left) == s.charAt(right)) {
            char current = s.charAt(left);
            while(left <= right && s.charAt(left) == current) left++;
            while(left <= right && s.charAt(right) == current) right--;
        }
        return right - left + 1;
    }
}

class Solution:
    def minimumLength(self, s: str) -> int:
        left, right = 0, len(s) - 1
        while left < right and s[left] == s[right]:
            current = s[left]
            while left <= right and s[left] == current:
                left += 1
            while left <= right and s[right] == current:
                right -= 1
        return right - left + 1

Comparison of Approaches

Edge Cases and Special Considerations

When implementing solutions for this problem, consider these edge cases:

1. All Characters Same

Input: "aaaaa" → Output: 1
Explanation: Can remove all but one character

2. No Possible Operations

Input: "abc" → Output: 3
Explanation: No matching characters to perform operations

3. Alternating Characters

Input: "ababab" → Output: 6
Explanation: No operations possible due to alternation

Visualization

Frequently Asked Questions