Partition Labels | 2 Clean Approaches | Leetcode 763 | codestorywithMIK

Hi Everyone, this is the 9th video of our Playlist "Two Pointers : Popular Interview Problems".
Now we will be solving a good problem based on Two Pointers - Partition Labels | 2 Clean Approaches | Leetcode 763 | codestorywithMIK

We will start from scratch and cover everything in minute details. It might be lengthy but please see it at more speed if required.

Problem Name : Partition Labels | 2 Clean Approaches | Leetcode 763 | codestorywithMIK
Company Tags : Amazon, Meta

╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝

Video Summary :
Approach-1:
This approach first records the last occurrence of each character in the string. Then, it iterates through the string while expanding a partition until no character within it appears later in the string. Once a partition is finalized, its length is stored.

Approach-2:
This approach optimizes the first by maintaining a start pointer to track the beginning of each partition. It updates the end index dynamically and finalizes partitions whenever the current index matches the end, ensuring more efficient segmentation.

✨ Timelines✨
00:00 - Introduction
0:24 - Motivation
0:42 - Problem Explanation
2:46 - Simple Thought Process
8:21 - Complete Dry Run
18:54 - Coding it up
21:08 - Clear Approach
26:03 - Coding it up

#MIK #mik #Mik
#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview#interviewtips #interviewpreparation #interview_ds_algo #hinglish #github #design #data #google #video #instagram #facebook #leetcode #computerscience #leetcodesolutions #leetcodequestionandanswers #code #learning #dsalgo #dsa #coding #programming #100daysofcode #developers #techjobs #datastructures #algorithms #webdevelopment #softwareengineering #computerscience #pythoncoding #codinglife #coderlife #javascript #datascience #leetcode #leetcodesolutions #leetcodedailychallenge #codinginterview #interviewprep #technicalinterview #interviewtips #interviewquestions #codingchallenges #interviewready #dsa #hindi #india #hindicoding #hindiprogramming #hindiexplanation #hindidevelopers #hinditech #hindilearning #helpajobseeker #jobseekers #jobsearchtips #careergoals #careerdevelopment #jobhunt #jobinterview #github #designthinking #learningtogether #growthmindset #digitalcontent #techcontent #socialmediagrowth #contentcreation #instagramreels #videomarketing #codestorywithmik #codestorywithmick #codestorywithmikc #codestorywitmik #codestorywthmik #codstorywithmik #codestorywihmik #codestorywithmiik #codeistorywithmik #codestorywithmk #codestorywitmick #codestorymik #codestorwithmik

[llavishsheth]

Recently, I gave an interview at a product-based company, and I cleared the DSA round very easily—all thanks to you! Your approach of 'story to code' gave me the confidence that if I focus on understanding the logic, I can clear any round. In the second round, I was able to answer various questions with ease, though I lacked in some concepts that I need to work on.

I don’t know if I will get this job, but one thing I do know—I now have immense confidence that with consistency, anything is possible!

Thank you so much for teaching us. A lot of thanks and best wishes. Hope you grow more and more! ❤

Love from my side. ❤🔥

[coderbanda-ps]

I was so close to solving it. the problem statement in confusing in leetcode.
thanks for the dry run

[AdityaSharma-oxdv]

thankyou bhaiya, you are really my motivation

[Booksmadesimple]

i solved it on my own using mik's "story to code".Thank you mik for teaching how to approach problem❤❤.
at first i did a basic mistake, but understood it when 88th testcase failed.
class Solution {
public:
vector<int> partitionLabels(string s) {
int n = s.length();
vector<int> first(26, -1);
vector<int> last(26, -1);
for (int i = 0; i < n; i++) {
char ch = s[i];
int idx = ch - 'a';
if (first[idx] == -1) {
first[idx] = i;
}
last[idx] = i;
}
int end = -1;
vector<int> ans;
int i = 0, j = 0;
while (j < n) {
if (j == end) {
ans.push_back(j - i + 1);
i = j + 1;
} else {
char ch = s[j];
int idx = ch - 'a';
end = max(end, last[idx]);
}
j++;
}
return ans;
}
};

Here i used first vector to store first occurence of char but later realized it was of no use🙃.
Here is corrected code:-
class Solution {
public:
vector<int> partitionLabels(string s) {
int n = s.length();
//vector<int> first(26, -1);
vector<int> last(26, -1);
for (int i = 0; i < n; i++) {
char ch = s[i];
int idx = ch - 'a';
// if (first[idx] == -1) {
// first[idx] = i;
// }
last[idx] = i;
}
int end = -1;
vector<int> ans;
int i = 0, j = 0;
while (j < n) {
char ch = s[j];
int idx = ch - 'a';
end = max(end, last[idx]);
if (j == end) {
ans.push_back(j - i + 1);
i = j + 1;
}
j++;
}
return ans;
}
};

[ManaswiRane]

Day 44
Used two unordered maps firstidx and lastidx as bruteforce
just realised firstidx was not needed
gonna earn my first leetcode badge tomorrow...EXCITED!!!

[Anshul-qbpm]

sir i solved today's potd on my own using the merge intervals concept

[tuikasrivastava]

similar to the ques where we have to count the number of good partitions!

[sauravchandra]

When I saw the problem, I figured I would need to store the first and last occurrence of each alphabet. By looking the the intervals formed by the first and last element, I figured it would be similar to the merge intervals problem, and it did work. Here is the code:
class Solution:
def mergeIntervals(self, intervals):
mergedIntervals = []
currInterval = intervals[0]

for curStart, curEnd in intervals[1:]:
if curStart <= currInterval[1]:
currInterval[1] = max(currInterval[1], curEnd)
else:

currInterval = [curStart, curEnd]



res = []

for curStart, curEnd in mergedIntervals:


return res

def partitionLabels(self, s: str) -> List[int]:
mp = defaultdict(list)

for i in range(len(s)):
mp[s[i]].append(i)

intervals = []

for key in mp.keys():
intervals.append([mp[key][0], mp[key][-1]])

return

[salmanahmed]

I have solved this problem using the concept of merge intervals

i took strating and end position of every character as an interval

after merging i calculated intervals size thats our answer

[ashwinrao]

Nice Explanation MIK, I solved using slightly different approach using lastIndexOf in Java that implicity operates at O(n*k), here is the implementation. Though its a relatively slow solution due to the low constraints it was accepted.

public List<Integer> partitionLabels(String s) {
int n = s.length();
List<Integer> answer= new ArrayList<>();


for(int i = 0;i<n;i++){

char currChr = s.charAt(i);
int firstIdx = s.indexOf(currChr);
int lstIdx = s.lastIndexOf(currChr);

// check if the partition is valid
for(int j = firstIdx;j<=lstIdx;j++){
char inWindowChar = s.charAt(j);
firstIdx = Math.min(s.indexOf(inWindowChar), firstIdx);
lstIdx = Math.max(s.lastIndexOf(inWindowChar), lstIdx);
}



while (i<lstIdx){
i++;
}

}

return answer;

}

[vivek.tiwary]

Sharing a thought here, we could just track the frequency, and for a winow if all the frequency of element becomes zero, that is valid partition. Got it accpeted, but has extra overhead of O(N)

public class Solution
{
public IList<int> PartitionLabels(string s)
{
var freq = new Dictionary<char, int>();
foreach (char ch in s)
if (!freq.TryAdd(ch, 1))
freq[ch]++;

IList<int> ans = new List<int>();

//for partition we need both l, r to get the length
var unique = new HashSet<char>();
for (int r = 0, l = 0; r < s.Length; r++)
{
char right = s[r];
unique.Add(right);
if (--freq[right] == 0)
unique.Remove(right);
if (unique.Count == 0)
{
ans.Add(r - l + 1);
l = r + 1;
}
}

return ans;
}


}

[GauravKumar-lbze]

Solved using Sliding Window

class Solution:
def partitionLabels(self, s: str) -> List[int]:
i=0
j=0

mp = {}
st = set()
n = len(s)
vtr = []
for t in s:
mp[t] = mp.get(t, 0) + 1


while j<n:
mp[s[j]] -= 1
st.add(s[j])

if(mp[s[j]] == 0):
del mp[s[j]]
st.remove(s[j])


if(len(st)==0):
vtr.append(j-i+1)
i=j+1


j += 1


if len(st)>0:
vtr.append(j-i+1)

return vtr

[pranavch]

Do you use int n = s.size(); for clarity? I'm asking because .size() for all containers in std is O(1).

[bandariAkshay-jslv]

class Solution {
public:
vector<int> partitionLabels(string s) {
vector<int>ans;
vector<int>count1(26, 0);
vector<int>count2(26, 0);
int l = s.length() ;
for(int i=0;i< l; i++){
count1[s[i]-'a']++;
}
int prevValIdx =-1;
for(int i =0;i<l ; i++ ){
count2[s[i]-'a']++;
bool validSplit = true;
for(int j=0;j< 26 ; j++){

if(count2[j] >0 && count2[j]!= count1[j]) {
validSplit = false; break;
}
}
if(validSplit) {

ans.push_back(i-prevValIdx);
prevValIdx = i;
}
}
return ans;
}
};

[anshulverma]

Simple java code


List<Integer> list = new ArrayList<>();
int x = 0;
int prev = 0;
for (int i = 0; i < s.length(); i++) {

x = Math.max(x, s.lastIndexOf(s.charAt(i)));
if (x == i) {
if(list.isEmpty()) {
list.add(x-prev+1);}
else {

}
prev = i;
}

}
return list;

[Akashkumar_]

my solution
class Solution {
public:
vector<int> partitionLabels(string s) {
int n=s.size();
vector<int>ans;
map<char, vector<int>>mp;
for(int i=0;i<n;i++){
char ch=s[i];
mp[ch].push_back(i);
}
int prev=INT_MIN;
int sum=0;
for(char &ch:s){
auto &vec=mp[ch];
if(prev==INT_MIN){
prev=max(prev, vec.back());
}
else if(prev<vec.front()){

sum+=ans.back();
}
prev=max(prev, vec.back());
}
ans.push_back(prev-sum+1);
return ans;
}
};

[YourTechnoByte]

I did this with Merge Intervals Concept LOL, then I thought I did it. But your explained solution is more optimized.

[utkarsh-kp]

SIr One request, If possible ho to aap sunday wale leetcode ke contest ka 3rd and 4th question upsolve kr skte hain kyaa.. Bhaut help ho jaaayegi

[ramyapujitha]

When i read que for the first time i thought it was a recursion based que
Have anyone of u thought the same???

[srijandas]

can be solved using merge intervals approach ig.