Remove Duplicate Letters | Leetcode

This video explains a very important programming interview problem which is based on a monotonic stack. I have explained the problem statement with intuition for why should we maintain an increasing order of the elements and then I have also explained why do we need other data structures like frequency array and a visited array.
CODE LINK is present below as usual. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :)
======================================PLEASE DONATE=============================
🧡 SUPPORT OUR WORK: / techdose
💚 UPI-ID: surya.kahar@ybl
💞JOIN Membership: / @techdose4u
==============================================================================
INSTAGRAM : / surya.pratap.k
LinkedIn: / surya-pratap-kahar-47b...
WEBSITE: techdose.co.in/
TELEGRAM Group LINK: t.me/joinchat/SRVOIxWR4sRIVv5...
=======================================================================
USEFUL LINKS:
🟠Must do TIPS to ACE Virtual Interview: • 🔴Must do Tips to ACE y...
🟢Best strategy to excel your coding interview: • 🔴Best strategy to exce...
🟡Get your dream job in 1 month: • 🔴Get your dream job in...
🔵How to crack dream job in just 2 months: • How to crack dream job...
🟣7 Days DSA plan: techdose.co.in/7-days-dsa-che...
RELATED LINKS:
Trapping Rainwater Problem: • Trapping Rainwater Pro...
CODE LINK: gist.github.com/SuryaPratapK/...

[@techdose4u]

🟣 JOIN our 𝐋𝐈𝐕𝐄 𝐢𝐧𝐭𝐞𝐫𝐯𝐢𝐞𝐰 𝐭𝐫𝐚𝐢𝐧𝐢𝐧𝐠 𝐩𝐫𝐨𝐠𝐫𝐚𝐦 through whatsapp query: [phone] 🔴 𝐂𝐡𝐞𝐜𝐤𝐨𝐮𝐭 𝐚𝐥𝐥 𝐨𝐮𝐫 𝐂𝐨𝐮𝐫𝐬𝐞𝐬: techdose.co.in/

[@MP-ny3ep]

The way you explained why we need a frequency set and a visited set is just phenomenal!

[@AjeetKumar-tt1jr]

I loved the way you approached the problem, just awesome... thanks

[@pritz9]

Clear And Concise!

[@vineetsharma2604]

Great explaination, thanks a lot!

[@AnkitKumar-ys7vs]

Thaks way of explanination is very good.

[@pryansh_]

thanks ! it was helpful.

[@thecricketerraja]

really very nicely explained , big thank you 🙏❤

[@techdose4u]

My pleasure 😊

[@ihsannuruliman3656]

Hi, could you make a video on Optimal Binary Search Tree? I've watched couple of videos on KZbin but it's still doesn't make sense to me. I think you're the best in terms of explaining.

[@chandrashekharagrawal4890]

Amazing explanation!!

[@rbk.technology4747]

Perfect perfect video. Understood.

[@maruthkamath9304]

How can the time complexity in this case be said to be just O(N) , when you may have to pop all elements of the stack for just placing 1 element. Would the pop operations not add up to the complexity?

[@techdose4u]

One letter can only be pushed and popped once. So, total push + pop can be 2N :)

[@agnesakne4409]

Great explanation.

[@satyamsrivastava2440]

phenomenal explanation

[@FullMetalAlgorithmist]

well explained.

[@pabitrakb5291]

Nice explanation

[@HarishKumar-bx8ht]

Hee once you have frequency array .. you can just traverse the freq array and check freq >0 then append to answer . Which will be more efficient right ?

[@adee6467]

Order won't be maintained

[@yaswanthp2294]

Lovely

[@houssemelhadj6881]

Thank for your work, doese your code actually at the end validate, (did you submit it ) it seems to me there maybe something missing. at the end you returned "bca" as answer and i thought the answer should be "abc". or do i need just to return the smallest substring, so that the order of them is given by the original string? for example: bacbab -> acb or abc ? anyway Thanks for your good work

[@techdose4u]

You need to return the smallest unique lettered subsequence. So answer will be acb.

[@houssemelhadj6881]

@@techdose4u yes yes i first missunderstood the problem, and finally did it myself in python ( around 90 % acceptance ) inspired by your method. I didn't use the visited list thought. I directly checked the stack if it holds the element before pushing or popping. and it worked blissfully :) very thanks

[@pankajmaurya64]

@@techdose4u After removing duplicate element from input "bcab", output will be "bca" -> according to leetcode

[@fazilshafi8083]

Java Solution -----> public class Solution { public String removeDuplicateLetters(String s) { Map freq = new HashMap(); for (int i = 0; i < s.length(); ++i){ char ch = s.charAt(i); freq.put(ch, freq.getOrDefault(ch, 0) + 1); } // Monotonic stack to maintain increasing order of chars Stack stack = new Stack(); Map seen = new HashMap(); // Track already included elements for (int i = 0; i < s.length(); ++i) { char ch = s.charAt(i); if (seen.containsKey(s.charAt(i))) { // Don't process already included char freq.put(ch, freq.get(ch) - 1); continue; } while (!stack.isEmpty() && stack.peek() > ch && freq.get(stack.peek()) > 0) { // Pop all possible larger chars seen.remove(stack.peek()); stack.pop(); } stack.push(ch); seen.put(ch, true); freq.put(ch, freq.get(ch) - 1); } StringBuilder ans = new StringBuilder(); while (!stack.isEmpty()) { ans.append(stack.pop()); } return ans.reverse().toString(); } }

[@yashagrawal1663]

is there a way to to solve this in linear space without taking a stack data structure

[@priyanshumaikhuri5856]

Yes, you could use string instead of stack

[@yashgoswami5374]

Can't we just put all chars in set and get unique, isn't it that simple

[@techdose4u]

Need to maintain order of elements as mentioned in string :)

[@pankajmaurya64]

@TECH DOSE After removing duplicate element from input "bcab", output will be "bca" -> according to leetcode

[@anonymous-sk2pr]

1st 😉😉😉

[@QuynhNhu-gu5ql]

hay chi chi rô

[@who_thekaushik]

bhai aisi vids bna ne se accha toh mat he bna