# Minimum Length of String After Operations
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-length-of-string-after-operations)
Canonical: https://scaleengineer.com/dsa/problems/minimum-length-of-string-after-operations
**Patterns:** [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Data structures:** Hash Table, String
**Companies:** [IBM](https://scaleengineer.com/companies/ibm)
---
## Problem
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** occurrence of `s[i]` located to the **left** of `i`.
* Delete the **closest** occurrence of `s[i]` located to the **right** of `i`.

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

**Example 1:**

**Input:** s = "abaacbcbb"

**Output:** 5

**Explanation:**  
We do the following operations:

* Choose index 2, then remove the characters at indices 0 and 3\. The resulting string is `s = "bacbcbb"`.
* Choose index 3, then remove the characters at indices 0 and 5\. The resulting string is `s = "acbcb"`.

**Example 2:**

**Input:** s = "aa"

**Output:** 2

**Explanation:**  
We cannot perform any operations, so we return the length of the original string.

**Constraints:**

* `1 <= s.length <= 2 * 105`
* `s` consists only of lowercase English letters.

# Approaches
## Brute-Force Simulation
This approach directly simulates the process described in the problem. It works by repeatedly scanning the string to find a valid operation—a character that has identical characters to its left and right. Upon finding one, it removes the closest left and right occurrences and then rescans the modified string. This continues until no more operations can be performed.
**Time:** O(N^3), where N is the initial length of the string. The outer `while` loop can execute up to O(N) times (as each operation removes 2 characters). Inside, finding an operation involves iterating through the list (O(N)) and, for each element, searching for neighbors (O(N)), leading to O(N^2) for one operation. Total complexity is O(N) * O(N^2) = O(N^3). · **Space:** O(N), where N is the length of the string, to store the `ArrayList` of characters.
**Pros:** It's a straightforward implementation of the problem's rules.; Easy to understand and reason about its correctness.
**Cons:** Extremely inefficient due to repeated, nested loops and costly list modification operations.; The time complexity of O(N^3) makes it infeasible for the given constraints, leading to a 'Time Limit Exceeded' error.
### Explanation
The brute-force simulation tackles the problem by mimicking the operations on a mutable data structure, like an `ArrayList` of characters. It enters a loop, and in each iteration, it searches for the first possible operation. A character `s[i]` can be a pivot if there's at least one `s[i]` to its left and one to its right. Once such a pivot is found, the algorithm removes the nearest left and right occurrences. Because this removal alters the string's length and indices, the search for the next operation must be restarted. The process halts when a full pass over the string yields no possible operations. The length of the resulting string is the answer.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public int minimumLength(String s) {
        List<Character> chars = new ArrayList<>();
        for (char c : s.toCharArray()) {
            chars.add(c);
        }

        while (true) {
            boolean operationPerformed = false;
            int leftIdx = -1;
            int rightIdx = -1;

            // Find the first possible operation in the current string state
            for (int i = 0; i < chars.size(); i++) {
                char currentChar = chars.get(i);
                int currentLeft = -1;
                for (int j = i - 1; j >= 0; j--) {
                    if (chars.get(j) == currentChar) {
                        currentLeft = j;
                        break;
                    }
                }

                if (currentLeft != -1) {
                    int currentRight = -1;
                    for (int j = i + 1; j < chars.size(); j++) {
                        if (chars.get(j) == currentChar) {
                            currentRight = j;
                            break;
                        }
                    }
                    if (currentRight != -1) {
                        leftIdx = currentLeft;
                        rightIdx = currentRight;
                        operationPerformed = true;
                        break; // Found an operation, break to perform it
                    }
                }
            }

            if (operationPerformed) {
                // Remove the elements, larger index first to avoid shifting
                chars.remove(rightIdx);
                chars.remove(leftIdx);
            } else {
                break; // No operations found in a full pass, we are done
            }
        }
        return chars.size();
    }
}
```
### Algorithm
*   Convert the input string `s` into a mutable list of characters, like an `ArrayList`.
*   Enter a main loop that continues as long as an operation was performed in the previous pass. A boolean flag, say `operationPerformed`, can track this.
*   Inside the loop, iterate through the character list to find a valid operation. For each character at index `i`, it's a potential pivot.
*   To check if `i` is a valid pivot, search for the same character to its left (from `i-1` down to `0`) and to its right (from `i+1` to the end).
*   If the closest occurrences are found at `leftIdx` and `rightIdx`, you have a valid operation.
*   Perform the operation by removing the characters at `rightIdx` and `leftIdx` from the list. It's crucial to remove the element with the larger index first to avoid shifting the other's index.
*   Set `operationPerformed` to `true` and restart the main loop's pass, as the list modification has changed indices.
*   If a full scan of the list completes without finding any valid operations, set `operationPerformed` to `false` and the main loop will terminate.
*   The final size of the list is the minimum length.

## Frequency Counting
This optimal approach is based on a crucial observation: the operations on one type of character do not affect the possibility of operations on another. The final length of the string is determined solely by the initial frequency of each character. By analyzing the removal pattern, we can directly calculate how many characters of each type will remain after all possible operations are performed.
**Time:** O(N), where N is the length of the string. This is because we only need a single pass over the string to count character frequencies. The subsequent loop over the frequency map is constant time (26 iterations). · **Space:** O(1), as the frequency map (an array of size 26) does not depend on the input string's size.
**Pros:** Extremely efficient with linear time complexity.; Requires constant extra space.; Simple and concise to implement once the pattern is understood.
**Cons:** The solution relies on a key insight into the problem's structure, which may not be immediately obvious.
### Explanation
The key insight is that for any character, say 'a', with a count of `k`, we can perform operations as long as there are at least 3 'a's left. Each operation consumes two 'a's. This means we can repeatedly reduce the count by 2 until it's no longer possible (i.e., the count is less than 3). 

If the initial count `k` is odd (e.g., 5), the count will go `5 -> 3 -> 1`. One character remains. 
If the initial count `k` is even (e.g., 6), the count will go `6 -> 4 -> 2`. Two characters remain. 

This pattern holds for all characters. Therefore, we don't need to simulate the process at all. We can just count the initial frequencies of all characters and, for each character, calculate how many will remain. The sum of these remaining counts gives the minimum possible length of the final string.

```java
class Solution {
    public int minimumLength(String s) {
        int[] counts = new int[26];
        for (char c : s.toCharArray()) {
            counts[c - 'a']++;
        }

        int minLength = 0;
        for (int k : counts) {
            if (k > 0) {
                // If k is odd, 1 character remains.
                // If k is even, 2 characters remain.
                if (k % 2 == 1) {
                    minLength += 1;
                } else {
                    minLength += 2;
                }
            }
        }
        return minLength;
    }
}
```
### Algorithm
*   Realize that operations for a specific character are independent of other characters.
*   For any character `c` with `k` occurrences, an operation is possible if `k >= 3`. Each operation reduces `k` by 2.
*   This means we can keep removing pairs of `c` until its count is either 1 or 2.
*   If the initial count `k` is odd, the final count will be 1.
*   If the initial count `k` is even and positive, the final count will be 2.
*   The algorithm is as follows:
    1.  Create a frequency array `counts` of size 26 for the lowercase English letters.
    2.  Iterate through the input string `s` once to populate the `counts` array.
    3.  Initialize a result variable `minLength = 0`.
    4.  Iterate through the `counts` array. For each count `k > 0`:
        *   If `k` is odd, add 1 to `minLength`.
        *   If `k` is even, add 2 to `minLength`.
    5.  Return `minLength`.

# Solutions
### Java

```java
class Solution {
public
  int minimumLength(String s) {
    int[] cnt = new int[26];
    for (int i = 0; i < s.length(); ++i) {
      ++cnt[s.charAt(i) - 'a'];
    }
    int ans = 0;
    for (int x : cnt) {
      if (x > 0) {
        ans += x % 2 == 1 ? 1 : 2;
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minimumLength(string s) {
    int cnt[26]{};
    for (char &c : s) {
      ++cnt[c - 'a'];
    }
    int ans = 0;
    for (int x : cnt) {
      if (x) {
        ans += x % 2 ? 1 : 2;
      }
    }
    return ans;
  }
};

```

### Python

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

```