# Repeated Deletion Sequel - Amazon Top Interview Questions

### Problem Statement :

```Given a string s and an integer k, repeatedly delete the earliest k consecutive duplicate characters.

Constraints

k, n ≤ 100,000 where n is the length of s.

Example 1

Input

s = "baaabbdddd"

k = 3

Output

"d"

Explanation

First we delete the "a"s to get "bbbdddd". Then we delete the "b"s to get "dddd". Then we delete three of
the four "d"s to get "d"```

### Solution :

```                        ```Solution in C++ :

string solve(string s, int k) {
if (k == 1) return "";
vector<pair<int, char>> stack{{0, '#'}};

for (auto &c : s) {
if (stack.back().second != c) {
stack.push_back({1, c});
} else if (++stack.back().first == k) {
stack.pop_back();
}
}

string result = "";

for (int i = 1; i < stack.size(); i++) {
for (int j = 0; j < stack[i].first; j++) {
result += stack[i].second;
}
}

return result;
}```
```

```                        ```Solution in Java :

import java.util.*;
class pair { // created  a class pair to store char and its count.
char val;
int num;
pair(char val, int num) {
this.val = val;
this.num = num;
}
}
class Solution {
public String solve(String s, int k) {
Stack<pair> st = new Stack<>(); // stack which has pair as attribute.

for (int i = 0; i < s.length(); i++) {
if (st.isEmpty()) { // check if stack is empty then simply push with count 1.
st.push(new pair(s.charAt(i), 1));
} else if (s.charAt(i)
== st.peek().val) { // check if incoming value is equal to peak value or not.
st.push(new pair(s.charAt(i), st.peek().num + 1));
// if its equal to stack top value, we'll insert this into stack with count 1+ of
// peek.
} else {
st.push(new pair(
s.charAt(i), 1)); // last entered char was different so simply push with 1.
}
if (st.peek().num == k) { // if we arrive to that point where top value count = k.
int x = st.peek().num;
while (x > 0) { // we will pop all k values from stack.
st.pop();
x--;
}
}
}
String fin = ""; // answer string.
while (st.size() > 0) { // while we dont get empty stack.
fin = st.pop().val + fin;
}
return fin;
}
}```
```

```                        ```Solution in Python :

class Solution:
def solve(self, s, k):
stack = []

for c in s:
if stack and c == stack[-1]:
stack[-1] += 1
else:
stack.append([c, 1])

if stack[-1] == k:
stack.pop()

return "".join([x * f for x, f in stack])```
```

## Delete a Node

Delete the node at a given position in a linked list and return a reference to the head node. The head is at position 0. The list may be empty after you delete the node. In that case, return a null value. Example: list=0->1->2->3 position=2 After removing the node at position 2, list'= 0->1->-3. Function Description: Complete the deleteNode function in the editor below. deleteNo

## Print in Reverse

Given a pointer to the head of a singly-linked list, print each data value from the reversed list. If the given list is empty, do not print anything. Example head* refers to the linked list with data values 1->2->3->Null Print the following: 3 2 1 Function Description: Complete the reversePrint function in the editor below. reversePrint has the following parameters: Sing

Given the pointer to the head node of a linked list, change the next pointers of the nodes so that their order is reversed. The head pointer given may be null meaning that the initial list is empty. Example: head references the list 1->2->3->Null. Manipulate the next pointers of each node in place and return head, now referencing the head of the list 3->2->1->Null. Function Descriptio