Solve Leetcode Problems | Remove All Adjacent Duplicates in String II

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.

	Year	Company name	Designation	Status	Base Salary	Joining Bonus	Extras	Total CTC(INR)	Total CTC(USD)
	2016	Flipkart	SDE 1	Did not join	18 lakhs	2 lakhs	-	20 lakhs	27,420
	2016	Samsung Noida	SDE 1	Joined	14 lakhs	5 lakh	-	19 lakhs	26,050
	2017	Oyorooms	SDE 1	Joined	17 lakhs	-	-	17 lakhs	23,300
	2019	Sharechat	SDE 1	Joined	26 lakhs	2.6 lakhs	Stock options	28.6 lakhs	39,200
	2019	Grab	SDE 1	Did not join	21 lakhs	3 lakhs	-	24 lakhs	32,900
	2019	Rivigo	SDE 1	Did not join	27 lakhs	-	3 lakhs bonus	30 lakhs	41,100
	2020	Amazon	SDE 2	Did not join	26.5 lakhs	18.5 lakhs	-	43 lakhs	58,950
	2020	Uber	SDE 2	Did not join	33 lakhs	5 lakhs	15 lakhs stocks	55 lakhs	75,400
	2020	Booking.com	Developer	Currently working	Can't disclose	Can't disclose	Can't disclose	Can't disclose	Can't disclose

view raw employment_history.csv hosted with ❤ by GitHub

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

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

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.

	class LC1209 {
	public String removeDuplicates(String str, int k) {
	// Dry run for the code
	// s = "deeedbbcccbdaa" ; k= 3;
	// i char stack Action
	// 0 d (d,1)
	// 1 e (d,1),(e,1)
	// 2 e (d,1),(e,2)
	// 3 e (d,1),(e,3) As e occurs thrice we pop it from the stack. stack becomes (d,1)
	// 4 d (d,2)
	// 5 b (d,2),(b,1)
	// 6 b (d,2),(b,2)
	// 7 c (d,2),(b,2),(c,1)
	// 8 c (d,2),(b,2),(c,2)
	// 9 c (d,2),(b,2),(c,3) As c occurs thrice we pop it from the stack, stack becomes (d,2),(b,2)
	// 10 b (d,2),(b,3) As b occurs thrice we pop it from the stack, stack becomes (d,2)
	// 11 d (d,3) As b occurs thrice we pop it from the stack, stack becomes empty
	// 12 a (a,1)
	// 13 a (a,2)
	// now we have a stack . we need to pop elements from the stack and add that character according to its occurance.
	// finally return the reserved string
	//A Stack which keeps all the characters of the string
	Stack<Node> stack = new Stack<>();
	for (int i=0;i<str.length();i++){
	//We take one character at a time from the string
	char c = str.charAt(i);
	//If we have an emoty string then we will push a pair <c,1> to the stack as char c occurs once in the stack.
	if(stack.isEmpty())
	stack.push(new Node(c,1));
	//
	else if (!stack.isEmpty() && stack.peek().count==k-1 && stack.peek().ch==c){
	stack.pop();
	}
	else if (!stack.isEmpty() && stack.peek().ch==c){
	Node curr = stack.pop();
	stack.push(new Node(c,curr.count+1));
	}else{
	stack.push(new Node(c,1));
	}
	}
	//This is optimized version to make a string . Using StringBuilder is optimal then using string concatnation
	StringBuilder sb = new StringBuilder();
	while (!stack.isEmpty()){
	Node curr = stack.pop();
	char c = curr.ch;
	int y = curr.count;
	for (int i=1;i<=y;i++)
	sb.append(c);
	}
	//Reverse the string to get the answer
	return sb.reverse(). toString();
	}
	//Node is a pair of character and frequenecy of the character. We use this class to put entries into the stack.
	static class Node {
	public char ch;
	public int count;
	public Node(char ch, int count) {
	this.ch = ch;
	this.count = count;
	}
	}
	}

view raw LC1209.java hosted with ❤ by GitHub

The python code is given below.

	class LC1209(object):
	def removeDuplicates(self, s, k):
	stack = []
	count = 0
	for c in s:
	if stack and c == stack[-1][0]:
	prev = stack.pop()[1]
	stack.append((c, prev + 1))
	if prev + 1 == k:
	stack.pop()
	else:
	count = 1
	stack.append((c, count))
	result = ''
	for char, count in stack:
	result += char * count
	return result

view raw LC1209.py hosted with ❤ by GitHub

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.

webtutsplus / LeetCode