Solve Leetcode Problems | Remove All Adjacent Duplicates in String II
Tags: algorithms, programming, career, computerscience
Published: 2021-01-28 16:23:39

Problem 1209. **Remove All Adjacent Duplicates in String II.**

In this series, I am going to solve Leetcode medium problems live with my friend, which you can see on our youtube channel, Today we will do Problem 1209. **Remove All Adjacent Duplicates in String II.**

A little bit about me, I have offers from **Uber India** and **Amazon India** in the past, and I am currently working for **Booking.com** in Amsterdam.

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/s5bkah60kdlzj704s68t.jpg)

## Youtube Discussion

Please comment here or on youtube, if you have any doubts
{% youtube XZZL_nJ21VU %}

## Motivation to Learn Algorithms

I have worked in India as a software developer for 4 years. I started learning algorithms and data structure from my 3rd year in college as I was from an Electronics background. Here is my salary progression over the years, (all in INR, Lakh per year)

2016: placement in **Flipkart** from college, IIT KGP(18 lakh base + 2 lakh bonus = **20** lakh). But the offer was delayed by 6 months, as Flipkart was going through some trouble, so I joined Samsung.

2016: **Samsung Noida**(off campus ) (14 lakh base + 5 lakh joining bonus = **19** lakh). They pay to IITians 19 lakh but other colleges 9-14 lakh for the same work, which is bogus.

2017: **Oyorooms** (**17** lakh fixed, no bonus, no stocks). I took a pay cut as I was not learning anything in Samsung, so joined Oyo.

2019: **Sharechat** (26 lakh fixed + 2.6lakh bonus + stock options) I joined Sharechat in Bangalore, as SDE1 , I also got offers from **Grab** (21 lakh fixed + 3 lakh bonus =**24 lakh**) and **Rivigo** (27 lakh fixed+3 lakh bonus = **30 lakh**).

2020: Offer from Amazon ( 26.5 lakh base + 18.5 lakh joining bonus= **43 lakh**) in SDE2 role. They offer stocks but it is vested only 5 percent in the first year, so I ignored it.

Offer from **Uber** (33 lakh base + 15 lakh stock options per year (96000 USD over 4 years)+ 5 lakh joining bonus = **55** lakh per year) in SDE2 role. **I think that is the top salary, you can get 3.5–4 years experience in India, but I might be wrong.**
{% gist https://gist.github.com/sksaikia/b3e44a32bab220f3773ca25ba9b9adf2.js %}
I rejected both offers and ended up joining **Booking.com** as I wanted to explore Europe. I can’t disclose my current salary.

`A lot of startups and established companies in India pay over 35 lakh per year for the top talent in programming, for just over 4 years of experience, like Dunzo, Dream11, Rubric, etc, check`

[Compensation](https://leetcode.com/discuss/compensation)

Even if you are not from a good college, you can still land awesome jobs, for let’s take this example

`
Education: B.Tech in CS from Tier 3 college
Years of Experience: 2
Prior Experience: Java Developer at Startup
current CTC: INR 3.2 LPA+1 LPA(Bonus)
Date of the Offer:Dec 2020
Company: Swiggy
Title/Level:SDE -1
Location: Bangalore
Salary: INR 17.6 LPA
Relocation/Signing Bonus: -
Stock bonus: 7 LPA vested over 4 years
Bonus: -
Total comp (Salary + Bonus + Stock): 17.6 + 0 + 1.75 =INR 19.35 LPA
Benefits: -
Other details: Not even a single word from me after this digits are spoken by the recruiter.
`
**Has a 6 months career gap even at the time of offer**


I got so many offers because I practiced a lot of data structure and algorithms. I solved over 410 questions in Leetcode.

[Nil Madhab-Leetcode Profile](https://leetcode.com/nilmadhab/)

## Problem statement:

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"`

## Solution

This problem can be solved by using a stack. If we count the occurrence of each character and store it in a stack and as soon as the occurrence of that character becomes equal to k, we remove it from the stack. As we have stored the characters and their occurrence in a stack, we can pop it from the stack and reverse the generated string from the stack. (Reversal is necessary, just to a dry run of example 4).

The java code along with a dry run of example 3 for this problem is given below.
{% gist https://gist.github.com/sksaikia/9b5a74ae09769ce5cd42b4473cc4e6bd.js %}

The python code is given below.

{% gist https://gist.github.com/sksaikia/cb80d916ccea8415855da834772ca016.js %}

Time Complexity: O(n), n is the length of the string

Space Complexity: O(n), n is the length of the string

The solution code can be found in this repository.

{% github webtutsplus/Leetcode %}