Given a string s
, a k duplicate removal consists of choosing k
adjacent and equal letters from s
and removing them causing the left and the right side of the deleted substring to concatenate together.
We repeatedly make k
duplicate removals on s
until we no longer can.
Return the final string after all such duplicate removals have been made.
It is guaranteed that the answer is unique.
Example 1:
Input: s = "abcd", k = 2 Output: "abcd" Explanation: There's nothing to delete.
Example 2:
Input: s = "deeedbbcccbdaa", k = 3 Output: "aa" Explanation: First delete "eee" and "ccc", get "ddbbbdaa" Then delete "bbb", get "dddaa" Finally delete "ddd", get "aa"
Example 3:
Input: s = "pbbcggttciiippooaais", k = 2 Output: "ps"
Constraints:
1 <= s.length <= 10^5
2 <= k <= 10^4
-
s
only contains lower case English letters.
删除字符串中的所有相邻重复项 II。题意跟版本一差不多,但是这道题不只是删除重复元素,而是如果某个字符重复了K次才删除。我这里提供三种做法,大体思路都是需要操作StringBuilder来删除重复元素。
暴力。遍历input字符串,同时用一个count变量记录当前重复字母出现的次数,如果count == K,则去StringBuilder里面删除这一段(i - k + 1, i + 1)。注意删除操作的区间也是左闭右开的。
时间O(n)
空间O(n)
Java实现
1 class Solution { 2 public String removeDuplicates(String s, int k) { 3 StringBuilder sb = new StringBuilder(s); 4 int len = -1; 5 while (len != sb.length()) { 6 len = sb.length(); 7 for (int i = 0, count = 1; i < sb.length(); i++) { 8 if (i == 0 || sb.charAt(i) != sb.charAt(i - 1)) { 9 count = 1; 10 } else { 11 count++; 12 if (count == k) { 13 sb.delete(i - k + 1, i + 1); 14 break; 15 } 16 } 17 } 18 } 19 return sb.toString(); 20 } 21 }
计数。这里我们需要用到一个额外数组记录到当前位置,出现了多少次重复字母。当发觉count[i] == K的时候,也是去StringBuilder里面删除这一段(i - k + 1, i + 1),同时i要往回退K步。
时间O(n)
空间O(n)
Java实现
1 class Solution { 2 public String removeDuplicates(String s, int k) { 3 StringBuilder sb = new StringBuilder(s); 4 int[] count = new int[sb.length()]; 5 for (int i = 0; i < sb.length(); i++) { 6 if (i == 0 || sb.charAt(i) != sb.charAt(i - 1)) { 7 count[i] = 1; 8 } else { 9 count[i] = count[i - 1] + 1; 10 if (count[i] == k) { 11 sb.delete(i - k + 1, i + 1); 12 i = i - k; 13 } 14 } 15 } 16 return sb.toString(); 17 } 18 }
栈stack。遍历当前字符,如果当前字符跟之前一个字符不同,则往栈内push一个1;如果跟之前一个字符相同,则把栈顶元素拿出来 + 1再push回去。此时如果count == K了,还是需要去StringBuilder里面删除这一段(i - k + 1, i + 1),同时i要往回退K步。
时间O(n)
空间O(n)
Java实现
1 class Solution { 2 public String removeDuplicates(String s, int k) { 3 StringBuilder sb = new StringBuilder(s); 4 Deque<Integer> stack = new ArrayDeque<>(); 5 for (int i = 0; i < sb.length(); i++) { 6 if (i == 0 || sb.charAt(i) != sb.charAt(i - 1)) { 7 stack.push(1); 8 } else { 9 int count = stack.pop() + 1; 10 if (count == k) { 11 sb.delete(i - k + 1, i + 1); 12 i = i - k; 13 } else { 14 stack.push(count); 15 } 16 } 17 } 18 return sb.toString(); 19 } 20 }
相关题目
1047. Remove All Adjacent Duplicates In String
1209. Remove All Adjacent Duplicates in String II