最小化字符串长度
难度:
标签:
题目描述
Given a 0-indexed string s, repeatedly perform the following operation any number of times:
- Choose an index
iin the string, and letcbe the character in positioni. Delete the closest occurrence ofcto the left ofi(if any) and the closest occurrence ofcto the right ofi(if any).
Your task is to minimize the length of s by performing the above operation any number of times.
Return an integer denoting the length of the minimized string.
Example 1:
Input: s = "aaabc" Output: 3 Explanation: In this example, s is "aaabc". We can start by selecting the character 'a' at index 1. We then remove the closest 'a' to the left of index 1, which is at index 0, and the closest 'a' to the right of index 1, which is at index 2. After this operation, the string becomes "abc". Any further operation we perform on the string will leave it unchanged. Therefore, the length of the minimized string is 3.
Example 2:
Input: s = "cbbd" Output: 3 Explanation: For this we can start with character 'b' at index 1. There is no occurrence of 'b' to the left of index 1, but there is one to the right at index 2, so we delete the 'b' at index 2. The string becomes "cbd" and further operations will leave it unchanged. Hence, the minimized length is 3.
Example 3:
Input: s = "dddaaa" Output: 2 Explanation: For this, we can start with the character 'd' at index 1. The closest occurrence of a 'd' to its left is at index 0, and the closest occurrence of a 'd' to its right is at index 2. We delete both index 0 and 2, so the string becomes "daaa". In the new string, we can select the character 'a' at index 2. The closest occurrence of an 'a' to its left is at index 1, and the closest occurrence of an 'a' to its right is at index 3. We delete both of them, and the string becomes "da". We cannot minimize this further, so the minimized length is 2.
Constraints:
1 <= s.length <= 100scontains only lowercase English letters
代码结果
运行时间: 28 ms, 内存: 16.1 MB
/*
题目思路：
使用 Java Stream API 来移除相同字符左侧和右侧最近的字符。
通过递归或迭代的方式，移除能够匹配的字符对。
*/
import java.util.stream.Collectors;
import java.util.stream.IntStream;
public class Solution {
public int minimizeStringLength(String s) {
while (true) {
int initialLength = s.length();
s = IntStream.range(0, s.length())
.filter(i -> (i == 0 || s.charAt(i) != s.charAt(i - 1)) && (i == s.length() - 1 || s.charAt(i) != s.charAt(i + 1)))
.mapToObj(i -> String.valueOf(s.charAt(i)))
.collect(Collectors.joining());
if (s.length() == initialLength) break;
}
return s.length();
}
}
解释
方法:
本题解的核心思想是利用集合（set）来去除字符串中的重复字符。每个字符至多保留一个实例，因为题目操作允许删除相邻的同字符。因此，最终字符串的长度将等于字符串中不同字符的数量。这种方法假设每个字符的所有相邻重复都将被删除，仅留下一个独立的字符实例。
时间复杂度:
O(n)
空间复杂度:
O(n)
代码细节讲解
🦆
题解中使用集合去重的方法似乎没有考虑到字符间的相对位置和删除规则，这种方法在所有情况下都有效吗？
▷🦆
在示例中的输入 'aaabc'，如果按照题解方法只计算不同字符的数量，输出为3，但是具体的删除步骤是怎样的？能否详细解释一下？
▷🦆
题解中提到每个字符的所有相邻重复将被删除，但在一些情况下，例如字符间隔出现的单个字符如何处理？例如 'ababa' 该如何最小化长度？
▷