[LeetCode] 1750. Minimum Length of String After Deleting Similar Ends

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’.

删除字符串两端相同字符后的最短长度。

给你一个只包含字符 ‘a’，’b’ 和 ‘c’ 的字符串 s ，你可以执行下面这个操作（5 个步骤）任意次：

1. 选择字符串 s 一个 非空 的前缀，这个前缀的所有字符都相同。
2. 选择字符串 s 一个 非空 的后缀，这个后缀的所有字符都相同。
3. 前缀和后缀在字符串中任意位置都不能有交集。
4. 前缀和后缀包含的所有字符都要相同。
5. 同时删除前缀和后缀。
   请你返回对字符串 s 执行上面操作任意次以后（可能 0 次），能得到的 最短长度 。

思路

根据题目描述的意思，不难想到思路是双指针从两边往中间逼近。这道题需要想清楚最后的细节，一共三种 case，
如果字符串不是回文或者中间部分不是回文，该返回什么长度
这种 case 最简单，就是返回左指针和右指针的间距 + 1 即可，参考这个例子

a	b	c	d
l			r

这个 case 的长度是 4，其实就等于 right - left + 1

如果字符串本身就是回文，且是类似abba这种形式的，该返回什么长度？
如果字符串本身就是回文但是长度是偶数，那么最后左指针和右指针会交错，因为 while 循环需要保证 left <= right

a	b	b	a
	r	l	

如果字符串本身就是回文，且是类似aba这种形式的，该返回什么长度？
如果字符串本身就是回文但是长度是奇数，比如这种极端的例子，此时我们开始移动 l 指针的时候，最后左指针和右指针也会交错

a	a	a
l		r

你会发现这三种 case 最后都可以返回 right - left + 1。

复杂度

时间O(n)
空间O(1)

代码

Java实现

class Solution {
    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);
			while (left <= right && s.charAt(left) == c) {
				left++;
			}
			while (left <= right && s.charAt(right) == c) {
				right--;
			}
		}
		return right - left + 1;
    }
}