Sponsored
Sponsored
This approach utilizes a stack data structure to track characters and their counts. As we iterate through the string, we push characters with their current counts on the stack. When the count of the top character in the stack reaches k, we pop the character from the stack to simulate removal of duplicates.
Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(n), for the stack and auxiliary storage.
1import java.util.Stack;
2
3public class Solution {
4 public String removeDuplicates(String s, int k) {
5 Stack<int[]> count = new Stack<>();
6 StringBuilder sb = new StringBuilder();
7 for (char ch : s.toCharArray()) {
8 if (!sb.isEmpty() && sb.charAt(sb.length() - 1) == ch) {
9 count.peek()[0]++;
10 } else {
11 sb.append(ch);
12 count.push(new int[]{1});
13 }
14 if (count.peek()[0] == k) {
15 sb.delete(sb.length() - k, sb.length());
16 count.pop();
17 }
18 }
19 return sb.toString();
20 }
21}
22
23class Main {
24 public static void main(String[] args) {
25 Solution solution = new Solution();
26 System.out.println(solution.removeDuplicates("deeedbbcccbdaa", 3)); // Output: aa
27 }
28}
29In this Java solution, a Stack is used to keep track of the consecutive count of characters. The StringBuilder is used to append characters and simulate stack functionality. When the count reaches k, the characters are deleted from the StringBuilder.
This approach utilizes a two-pointer technique to modify the string in place. Here, we treat the string as a character array, using one pointer to scan the input and another to build the output string. A helper array is used to store counts of consecutive characters.
Time Complexity: O(n)
Space Complexity: O(n)
1
This Java solution uses in-place replacement to efficiently remove duplicates. The stack character array and count integer array allow tracking and handling of repeated sequences directly within the input array.