Optimal Partition of String - Leetcode 2405

Optimal Partition of String - Leetcode 2405 - Python

Рет қаралды 13,547

NeetCodeIO

Күн бұрын

Пікірлер: 37

@the8426 Жыл бұрын

I love when I solve the problem first and watch your video after and we have the same solution!

@AustinWeeks Ай бұрын

Right, makes me feel like a wizard!

@Casardo Жыл бұрын

I was not that great with algo & ds, so I have been doing leetcode consistently since February. I (that was rejected at HRT's, Google's and Citadel's Internships OA) am starting to feel the difference that consistently coding is making (it is probably to soon to say that), but I just wanted to share this and thank you for your videos. They are very helpful

@adarshsasidharan254 Жыл бұрын

consistency is key indeed

@walkerboy180 Жыл бұрын

have you been following along with just the neetcode videos? if not what have you done to feel confident?

@sumitsharma6738 Жыл бұрын

the energy you gave me "Welcome back" ...... motivates me

@danielchanja Жыл бұрын

Yeah I completely agree that sometimes you just need to drill down on the core of the problem, otherwise you're making it more complicated than it needs to be. Clean solution, well done!

@chirag_9121 5 ай бұрын

Have my coding round at Amazon. This video was a huge help on how to break down a problem!

@sandeepreddy1345 4 ай бұрын

Hi @chirag_9121 may I know how many rounds were there after your Online assesment?

@chirag_9121 4 ай бұрын

@@sandeepreddy1345 hi after passing the coding test, I had to give another online assessment based on Amazon Leadership Principles that lasts around 3 hours. But unfortunately I got rejected in this round. Because I applied for a graduate role, if I had cleared this test, the only thing left would be an HR interview rather than another in person coding round.

@patrickc.6183 Жыл бұрын

Great stuff NeetCode! There is also a set.clear() to clear Set objects in JS (Python as well), instead of recreating and reassigning in the if condition. It's a small optimization, but worth it 😀.

@adarshsasidharan254 Жыл бұрын

thanks

@patrickc.6183 Жыл бұрын

@@adarshsasidharan254 Glad it helped!

@NeetCodeIO Жыл бұрын

Thanks, good point!

@anusha3598 8 ай бұрын

NEETCODE U R MY MOST FAVE TEACHER IN THE WORLD !!

@levimatheri7682 4 ай бұрын

At first thought this was a DP problem 😂 I still think it can be done with DP, but greedy is much easier

@ChrisCox-wv7oo Жыл бұрын

I'd argue the space complexity is O(m) where m is the number of unique characters. Also, there's no indication that the character set is lowercase only from problem description. Could include Unicode characters etc. (EDIT : constraints are listed in actual LC problem description, is only lowercase alpha. pre-allocation point below still stands.) Just because there is a fixed upper bound space doesn't mean the space used is constant. No one says space complexity is O(Computer RAM). Same as Time Complexity. The string size is upper bound 1000 chars. An O(n) solution doesn't turn into O(1000) -> O(1) Unless you pre-allocate a vector / hashmap etc with a fixed size, the space required is not constant. It grows with number of unique characters.

@yashchamoli8695 Жыл бұрын

code in java class Solution { public int partitionString(String s) { HashSet set =new HashSet(); int count=0; for(int i=0;i

@DeathSugar Жыл бұрын

You can use just int instead actual hashset though

@yashchamoli8695 Жыл бұрын

@@DeathSugar how can you please elaborate

@DeathSugar Жыл бұрын

@@yashchamoli8695 you can use bit masks on integer to check. whethere character was already used or not. Will use a bit less memory and checks on average should be faster.

@vixguy Жыл бұрын

I got it immediately! im proud lol

@NeetCodeIO Жыл бұрын

Nice! 👍

@ko_specter4251 Жыл бұрын

wow I tried to come up with my own solution before watching the video and I came up with the same exact solution

@adithyang6672 Жыл бұрын

I think we can improve this by using xor and bit manipulation,

@rohanchess8332 Жыл бұрын

Hey Neetcode, can you explain why this solution accounts for the minimum number of substrings?

@shashanksingh4510 Жыл бұрын

you have to maximize the length of each substring which you generate....it will automatically reduce the maximum number of substrings required

@adarshsasidharan254 Жыл бұрын

The intuition is correct because there is no point in not adding a character if it is not present in the current substring. We should add it so that it forms larger substrings, resulting in a lower total number of substrings formed. (From Leetcode Editorial)