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.
Youtube Discussion
Please comment here or on youtube, if you have any doubts
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.
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
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.
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.
The python code is given below.
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.
Top comments (0)