leetcode
leetcode 1551 ~ 1600
删除字符串两端相同字符后的最短长度

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

难度:

标签:

题目描述

代码结果

运行时间: 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的左右两端在开始时不相同,则表明这两个字符不需要被删除作为相同的前后缀。在这种情况下,算法直接终止循环,因为没有找到可以删除的相同字符前后缀。最终返回的长度将是整个字符串的长度,即right - left + 1。
🦆
如果字符串s中间存在一个或多个字符与两端字符都不相同,这些字符会如何影响最终的最短长度?
如果字符串s的中间存在与两端字符都不相同的一个或多个字符,这些字符不会影响两端相同字符的删除过程。算法主要关注于删除两端相同的字符。一旦两端的字符不相同,中间的字符不会进一步影响处理,因此这些字符将被保留在最终的子字符串中,从而影响最短长度。
🦆
为什么在双指针遇到相同字符时选择跳过所有相同的字符,而不是逐个比较后再决定跳过?
这种方法是为了提高算法的效率。由于目标是删除两端相同的字符,如果左右指针指向相同的字符,则可以预设这两端的所有相同字符都是可删除的。因此,一次跳过所有相同的字符而不是逐个比较,可以减少比较的次数,从而减少算法的执行时间。这样做可以直接移动到下一个可能不同的字符,进一步检查是否有新的相同字符可以删除。
🦆
在算法处理过程中,如何确保移动指针后left始终小于等于right,以避免错误计算剩余子字符串的长度?
在移动left和right指针时,算法通过在while循环条件中检查left <= right来确保left始终小于等于right。这样的条件检查避免了left和right交叉的情况,从而防止了对剩余子字符串长度的错误计算。当left指针超过right指针时,循环终止,这意味着中间没有剩余的字符,或者所有可删除的字符都已被删除。

相关问题