Count Unique Characters of All Substrings of a Given String | Leetcode 828
ฝัง
- เผยแพร่เมื่อ 14 ต.ค. 2024
- This video explains a very important interview problem which is to Count Unique Characters of All Substrings of a Given String. This problem is a common Amazon, Microsoft interview problem. It is based on counting unique characters in all substrings of a string.
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 Channel LINK: t.me/codewithT...
TELEGRAM Group LINK: t.me/joinchat/...
=======================================================================
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...
RELATED LINKS:
CODE LINK: gist.github.co...
After struggling for hours with text solutions, finally understood it from this beautiful explanation.
Great :)
Same
Very good and planned explanation., Understood in a shot
Great ❤️
Your teaching style is awesome. Keep up the good work.
Very well explained! Thanks TechDose.
Thank you, your explanation was very easy to understand. You made a difficult problem somewhat easy, at least "medium".
This is a master piece thank you so much!
idea is:
Find contribution of each char in string
eg. ABCABDA
here we see A at starting: putting A in middle
Check LHS size = 1 & RHS side (as long as A is unique) 4
Doing 1*4 = 4 (gives contribution of first A)
Similarlily, do rest all chars and add up at the end!
How do we know this? Observation & Dry run to check!
-----------------------------------------------
Approach---
Create a MAP (for constant time lookup) of vector of occurence
A-> 0-3-6
B-> 1-4
C-> 2
D-> 5
Now, do add -1 before each vec and n after each vec in map
So that when we check for each occurence (since we know index)
we can do e.g.[0], 0-(-1) * (3-0) = 1
and for [6], (6-3)* (n-6) = 3*1 = 3
and [3], (3-0)*(6-3) = 3*3 = 9
ADDING UP, 1+3+9 = 13
Best Explanation with intution
Wonderful explanation❤
very smart!!!😀
Very Good Explanation!
how's the time complexity O(N)?
we have a list of list and for each list we count.
isn't it a time complexity near to O(N^2)?
He is using the list of lists where the first list size is fixed to 26 alphabets, thus a constant. The only time required is to traverse the inner list whose worst case is 'len_of_string', i.e. O(n).
Nice Explanation!!
Is interview prep course still live?
Yes
@@techdose4u Congratulations, for AIR 1 in google kick-start round D
@@techdose4u when the new batch get starting?
back after so long
Yep :)
👏👏
what is the name of the software you are using?
Avoid Flood In The City
please please please
explain this problem
why everyone is getting TLE ?
please please please
Thank you so much! Very well explained!