# 資訊

:::info
- Question: 1750. Minimum Length of String After Deleting Similar Ends
- From: Leetcode Daily Challenge 2024.03.05
- Difficulty: Medium
:::

---

# 目錄

:::info
[TOC]
:::

---

# 題目

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:

- Pick a non-empty prefix from the string `s` where all the characters in the prefix are equal.
- Pick a non-empty suffix from the string `s` where all the characters in this suffix are equal.
- The prefix and the suffix should not intersect at any index.
- The characters from the prefix and suffix must be the same.
- 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:
:::success
- Input: `s = "ca"`
- Output: 2
- Explanation: You can't remove any characters, so the string stays as is.
:::

> Example 2:
:::success
- 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:
:::success
- 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:
:::success
- 1 <= `s.length` <= $10^5$
- `s` only consists of characters `'a'`, `'b'`, and `'c'`.
:::

---

# 解法

## 概念

還是 Two pointers 的題目，簡單說就是如果頭尾相同，就開始 remove，值道不同在進到下一輪判斷，要注意的點有兩個：一個是所有移動途中都不能造成 index out of range，所以會看到第 8 行多了一個條件是 `l <= r`，如果少了這行加上類似 `"bbbbbbbbbbb"` 的測資就會出事，因為 `l` 會停不下來直接衝出去。另一個要注意的是類似 `"accbbbcca"` 這種測資，因為中間的 `bbb` 是可以刪掉的，如果少了像第 10、11 行的檢查，就會讓 `l != r`，而產生 output `< 0` 的結果

## 程式碼

class Solution:
    def minimumLength(self, s: str) -> int:
        l = 0
        r = len(s) - 1
        while l < r:
            if s[l] == s[r]:
                c = s[l]
                while l <= r and s[l] == c:
                    l += 1
                if l > r:
                    break
                while s[r] == c:
                    r -= 1
            else:
                break
        return r - l + 1

---

# 複雜度

## 時間複雜度

會走完整條 string，所以是 $O(n)$


## 空間複雜度

幾個簡單的小變數被宣告，像是 two pointers 和暫存字元的 `c`，所以是 $O(1)$