删除字符串两端相同字符后的最短长度
难度:
标签:
题目描述
代码结果
运行时间: 47 ms, 内存: 16.2 MB
/*
* Problem Statement: Given a string s consisting of characters 'a', 'b', and 'c',
* you can perform the following operation any number of times:
* 1. Choose a non-empty prefix where all characters are the same.
* 2. Choose a non-empty suffix where all characters are the same.
* 3. The prefix and suffix must not overlap.
* 4. The characters in the prefix and suffix must be the same.
* 5. Remove both the prefix and suffix.
* The goal is to return the shortest possible length of the string after performing these operations.
*/
import java.util.stream.IntStream;
public 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 currentChar = s.charAt(left);
// Move left pointer to the right using IntStream
left = IntStream.range(left, s.length()).filter(i -> s.charAt(i) != currentChar).findFirst().orElse(s.length());
// Move right pointer to the left using IntStream
right = IntStream.rangeClosed(0, right).map(i -> right - i).filter(i -> s.charAt(i) != currentChar).findFirst().orElse(-1);
}
return Math.max(0, right - left + 1);
}
}
解释
方法:
此题解通过使用双指针技术来从两端同时检查字符串。指针left从字符串的起始位置开始,而right从字符串的结束位置开始。目标是在两端找到相同的字符并删除它们。如果当前left和right指向的字符相同,那么这两个字符可以被看作是前缀和后缀。此时,我们向内移动左右两个指针,跳过所有与当前字符相同的字符。这个过程会一直持续到left大于right或者left和right指向的字符不相同为止。最后,返回剩余子字符串的长度,即right - left + 1。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
在双指针算法中,如果字符串s的左右两端开始时不相同,如何处理?
▷🦆
如果字符串s中间存在一个或多个字符与两端字符都不相同,这些字符会如何影响最终的最短长度?
▷🦆
为什么在双指针遇到相同字符时选择跳过所有相同的字符,而不是逐个比较后再决定跳过?
▷🦆
在算法处理过程中,如何确保移动指针后left始终小于等于right,以避免错误计算剩余子字符串的长度?
▷