# Minimum Length of String After Deleting Similar Ends
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-length-of-string-after-deleting-similar-ends)
Canonical: https://scaleengineer.com/dsa/problems/minimum-length-of-string-after-deleting-similar-ends
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers)
**Data structures:** String
---
## Problem
Given a string `s` consisting only of characters `'a'`, `'b'`, and `'c'`. You are asked to apply the following algorithm on the string any number of times:

1. Pick a **non-empty** prefix from the string `s` where all the characters in the prefix are equal.
2. Pick a **non-empty** suffix from the string `s` where all the characters in this suffix are equal.
3. The prefix and the suffix should not intersect at any index.
4. The characters from the prefix and suffix must be the same.
5. Delete both the prefix and the suffix.

Return _the **minimum length** of_ `s` _after performing the above operation any number of times (possibly zero times)_.

**Example 1:**

**Input:** s = "ca"
**Output:** 2
**Explanation:** You can't remove any characters, so the string stays as is.

**Example 2:**

**Input:** s = "cabaabac"
**Output:** 0
**Explanation:** An optimal sequence of operations is:
- Take prefix = "c" and suffix = "c" and remove them, s = "abaaba".
- Take prefix = "a" and suffix = "a" and remove them, s = "baab".
- Take prefix = "b" and suffix = "b" and remove them, s = "aa".
- Take prefix = "a" and suffix = "a" and remove them, s = "".

**Example 3:**

**Input:** s = "aabccabba"
**Output:** 3
**Explanation:** An optimal sequence of operations is:
- Take prefix = "aa" and suffix = "a" and remove them, s = "bccabb".
- Take prefix = "b" and suffix = "bb" and remove them, s = "cca".

**Constraints:**

* `1 <= s.length <= 105`
* `s` only consists of characters `'a'`, `'b'`, and `'c'`.

# Approaches
## Iterative String Manipulation
This approach directly simulates the process described in the problem. It repeatedly finds the prefix and suffix with identical characters, removes them by creating a new substring, and continues this process in a loop until no more characters can be removed. While intuitive, this method is inefficient because string manipulation, especially creating substrings in a loop, is computationally expensive.
**Time:** O(N^2) in the worst case. For a string like "abacada...", each step removes only a few characters, and creating a substring can take O(N) time. With up to O(N) such steps, the total time is quadratic. · **Space:** O(N), where N is the length of the string. In each iteration, `substring` can create a new string object, potentially of length O(N).
**Pros:** Simple to understand and implement as it directly models the problem statement.
**Cons:** Highly inefficient due to the overhead of creating new string objects in each iteration.; Worst-case time complexity is quadratic, which is too slow for large inputs.; Can lead to high memory consumption due to the creation of many temporary string objects.
### Explanation
The algorithm works on the string `s` iteratively. In each iteration, it checks if the string has more than one character and if its first and last characters match. If they do, it identifies the common character `c`. It then finds the first index `left` that does not contain `c` from the beginning and the last index `right` that does not contain `c` from the end. If the `left` pointer crosses the `right` pointer, it implies the entire string consisted of the character `c`, and the resulting length is 0. Otherwise, the string `s` is updated to the substring between `left` and `right`. The loop continues until the ends don't match or the string becomes too short. Finally, the length of the resulting string `s` is returned.

```java
public int minimumLength(String s) {
    while (s.length() > 1 && s.charAt(0) == s.charAt(s.length() - 1)) {
        char c = s.charAt(0);
        int left = 0;
        int right = s.length() - 1;
        
        while (left <= right && s.charAt(left) == c) {
            left++;
        }
        
        // This check is crucial for strings like "aaaa"
        if (left > right) {
            return 0;
        }
        
        while (right >= left && s.charAt(right) == c) {
            right--;
        }
        
        s = s.substring(left, right + 1);
    }
    return s.length();
}
```
### Algorithm
*   Start a loop that continues as long as the string `s` has more than one character.
*   In the loop, check if the first and last characters of `s` are the same. If not, break the loop.
*   If they are the same, identify the character `c`.
*   Find the extent of the prefix of `c`'s by finding the first index `left` not equal to `c`.
*   Find the extent of the suffix of `c`'s by finding the last index `right` not equal to `c`.
*   If the entire string consists of `c` (i.e., `left` pointer moves past the `right` pointer), the result is 0.
*   Otherwise, update `s` by creating a new substring that excludes the identified prefix and suffix using `s.substring(left, right + 1)`.
*   After the loop terminates, return the length of the final string `s`.

## Two-Pointer Approach
A much more efficient approach uses two pointers, `left` and `right`, initialized to the start and end of the string, respectively. These pointers are moved inwards, skipping over the prefixes and suffixes that are to be deleted. This avoids the costly operation of creating new strings in each step, leading to an optimal linear time solution with constant space.
**Time:** O(N), where N is the length of the string. Each pointer, `left` and `right`, traverses the string at most once in a single pass. · **Space:** O(1). Only a constant amount of extra space is used for the two pointers and a character variable, regardless of the input string size.
**Pros:** Extremely efficient with linear time complexity.; Optimal space complexity, using only a constant amount of extra space.; Avoids expensive string creation and manipulation operations.
**Cons:** The logic with multiple nested loops and pointer updates might be slightly less intuitive to grasp initially compared to direct simulation.
### Explanation
This greedy algorithm uses two pointers, `left` starting at index 0 and `right` at `s.length() - 1`. The core of the algorithm is a `while` loop that runs as long as `left` is less than `right` and the characters at `s[left]` and `s[right]` are identical. This condition ensures we can perform an operation and that the prefix and suffix do not overlap.

Inside the loop:
1.  The common character `c` at the ends is noted.
2.  The `left` pointer is advanced forward past all consecutive occurrences of `c`.
3.  The `right` pointer is moved backward past all consecutive occurrences of `c`.

This process effectively "deletes" the prefix and suffix without actually modifying the string or creating new ones. The loop terminates when the characters at `left` and `right` are different, or when `left` meets or surpasses `right`. The final length of the remaining string is the number of characters between the final `left` and `right` positions, inclusive. This is calculated as `right - left + 1`. If `left` has moved past `right`, this formula correctly yields 0 or a negative number, which corresponds to an empty remaining string.

```java
public int minimumLength(String s) {
    int left = 0;
    int right = s.length() - 1;

    while (left < right && s.charAt(left) == s.charAt(right)) {
        char c = s.charAt(left);
        // Move left pointer to the right past all occurrences of c
        while (left <= right && s.charAt(left) == c) {
            left++;
        }
        // Move right pointer to the left past all occurrences of c
        while (right >= left && s.charAt(right) == c) {
            right--;
        }
    }
    
    // The remaining length is the distance between the two pointers
    return right - left + 1;
}
```
### Algorithm
*   Initialize two pointers: `left` at the start of the string (index 0) and `right` at the end (`s.length() - 1`).
*   Use a `while` loop that continues as long as `left < right` (to ensure prefix and suffix don't overlap) and `s.charAt(left) == s.charAt(right)`.
*   Inside the loop, save the character `c = s.charAt(left)`.
*   Increment `left` in a nested loop while `left <= right` and `s.charAt(left) == c` to skip the entire prefix.
*   Decrement `right` in another nested loop while `right >= left` and `s.charAt(right) == c` to skip the entire suffix.
*   Once the main loop terminates, the remaining part of the string is conceptually between indices `left` and `right`.
*   Return the length of this remaining part, which is calculated as `right - left + 1`.

# Solutions
### Java

```java
class Solution {
public
  int minimumLength(String s) {
    int i = 0, j = s.length() - 1;
    while (i < j && s.charAt(i) == s.charAt(j)) {
      while (i + 1 < j && s.charAt(i) == s.charAt(i + 1)) {
        ++i;
      }
      while (i < j - 1 && s.charAt(j) == s.charAt(j - 1)) {
        --j;
      }
      ++i;
      --j;
    }
    return Math.max(0, j - i + 1);
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minimumLength(string s) {
    int i = 0, j = s.size() - 1;
    while (i < j && s[i] == s[j]) {
      while (i + 1 < j && s[i] == s[i + 1]) {
        ++i;
      }
      while (i < j - 1 && s[j] == s[j - 1]) {
        --j;
      }
      ++i;
      --j;
    }
    return max(0, j - i + 1);
  }
};

```

### Python

```python
class Solution : def minimumLength ( self , s : str ) -> int : i , j = 0 , len ( s ) - 1 while i < j and s [ i ] == s [ j ]: while i + 1 < j and s [ i ] == s [ i + 1 ]: i += 1 while i < j - 1 and s [ j - 1 ] == s [ j ]: j -= 1 i , j = i + 1 , j - 1 return max ( 0 , j - i + 1 )
```