Prática de Shadowing: Minimum Window Substring - Airbnb Interview Question - Leetcode 76 - Aprenda a falar inglês com vídeo

Hey everyone, welcome back and let's write some more neat code today.

So today let's solve minimum window substring.

We're given two strings, s and t, and we want to return the minimum window in the string s,

which contains every single character present in string t.

And it's possible that that might not even exist, in which case we can return an empty string.

So in this case, our string S is this big long string, and our string T is this A, B, and C.

So we just need, we don't need to find A, B, C in here.

We just need to find a substring of S that contains all these characters, and we want to find the minimum string that contains all these characters.

So one possible string is this, right?

It has A, D, O, B, E, C.

So it has A, B, N, C.

But there happens to be a shorter string that has all of those as well.

This string, B, A, N, C.

So they are out of order.

So B, A, C.

And there's an N in there as well.

But this happens to be the shortest one.

It's length four.

And so that's the result that we're going to output.

So what's even a brute force way to solve this?

So we're given s and t right and we want like

if we're checking a substring right like this substring maybe this is our solution right how do we even determine

that well let's use some hash maps

so these two are our hash maps you can see i

have one for t what does this hash map represent well you look at t right

because for each of these substrings we just want to make sure

that it has at least one a right one a has at least one b

and it has at least one c

because that's what we have over here we just want to make sure

that we find the minimum substring in s that satisfies this condition

so for every possible window

that we check in s like maybe we check this window

we are going to want to have a hash map for the window

and we're going to count how many a's do we have initially we're going to start with zero right

because because initially our window is going to be just empty

or whatever we're going to start with zero b's and zero c's

but for this current window you can see we have one a one b

and one c right so we have one a one b

and one c so

so as we compare right we compare how many a's do

we have versus how many do we need right This is how many we need, and this is how many we have in our current window.

You can see we need one, and we have one, right?

So the relationship we're looking for is greater than or equal, right?

We want the counts all to be greater than or equal.

But one thing you can see is brute forcing is going to be difficult, right?

So let's say we initially start with this window, right?

See, we just added an A, so what are we going to do?

We're going to update this now let's just check is our window valid well we have at least one a

and so remembering that this is how many we have in our current window

and this is how many we need to satisfy the condition

so initially let's start with this window just one a

so then we can update our count for this window right add a single a

so now my question is have we satisfied the condition do

we have everything we need well how are we going to check

that well we have to check all of these right so

So is the have count greater than or equal to the need?

Yes, it is.

What about this?

Is the beat count greater than or equal to how many we need?

The answer is no, right?

So therefore, we don't have how many we need.

So therefore, we have to actually expand our window, right?

We have to add another character, this D, right?

But that's not actually going to update our window because we don't need any characters other than A, B, or C.

So we don't really care about the D.

The same thing is true for the O, but now we have a B, right?

That's good because we do need a B.

So we add a B.

So now we're going to have to run the same operation.

Do we have everything that we need?

So we're going to be doing some repeated work.

Do you notice this repeated work we're doing?

We have to check if we have enough A's, which we know we do because we already checked that when we first added this element.

So we notice we do have enough A's.

Do we have enough B's?

Well, this time we actually do because we just added a new B, right?

That's the most recent character we added.

Great.

So we know we have enough B's.

Do we have enough C's?

We do not have any C's in our string.

The count is zero.

Therefore, this condition is not met.

So we do not have our result yet.

We have an A and we have a B, but we need to add more.

so now we're going to add an e

which we don't really care about we're going to add a c

so finally we have so finally we can see

that we met our condition right

but we with our current algorithm our brute force way we have to repeatedly check every one of these even

if we already know the count is met

so this is basically where our repeated work this is what i'm going to show you how to eliminate

but as you can see we have enough a's we have enough b's we have enough sees.

So therefore, this is a possible result.

It might not be the minimum, but it's a possible result.

And what's the length of this?

It is six.

So we can say for now that our result is length six

and it goes from index zero all the way to index five.

100

So I'll put zero five.

101

That's our current result.

102

So one thing we noticed is we're having to do a lot of repeated work to check

103

that we have everything

104

that we need we have to check every single one of these characters right

105

but we don't we know we don't always have to do

106

that so let me show you how to do it without repeating all of

107

that work we're going to start out the same way

108

so we're going to add an a right that's our first character

109

so now we're going to check

110

so now what we're going to say is a count is one right

111

so now my question is do we have to check every single one of the halves

112

because initially we know that none of the conditions have been met, right?

113

Initially, we start with all zeros.

114

We also know that the number of characters that we need is going to be three, right?

115

Meaning we need to satisfy the count condition for three unique characters, right?

116

And we know that we start out with a half value of zero because we know for each of those three characters,

117

we have met the condition for none of them right initially we met the condition for none of them

118

because we start out with all zeros

119

but now you can see we just added an a

120

so let's check just for this one character have we met

121

the condition is the count greater than equal than one yes it is we have one

122

and we only needed one so we met the condition

123

so what does that mean we can take our have value and update it.

124

So initially it was zero.

125

Now we can change it to one.

126

So now we have one.

127

But my question now is, have we met the condition?

128

Well, we need three, but we only have one.

129

So we haven't met the condition.

130

You can see what I'm doing here, right?

131

Before we needed to check the condition for all three of these each time.

132

Now we only have to check the condition for one.

133

We have one value that tells us how many we have we have one value

134

that tells us how many we need

135

so before we were we had to continue running an operation of length t

136

which is in this case three

137

but who knows it could have been bigger t could have

138

been 10 it could have been a hundred it could have been anything

139

and we would be bounded by that but in this case we only have to do one operation for

140

comparing these integers and one operation for comparing the integers of the character that we just added.

141

So for each character that we add, we only have to do an O of one operation.

142

So now let's add another character.

143

Let's add the D.

144

We know that doesn't really do anything.

145

We add the O.

146

That doesn't do anything.

147

We add a B.

148

This is good.

149

So how am I going to do things differently this time?

150

Well, like usual, I'm going to change this one, this zero to a one.

151

We know we have one b

152

so now i'm going to check has this condition been met

153

or is it equal i know last time i showed you greater than

154

or equal but really what we're looking for is are they exactly equal

155

because that's when we know the condition has been met so

156

if these are exactly equal which they are in this case one equals one so what

157

that means is we can increment our half value by one

158

before it was it was one now we're going to actually change it to two

159

and now let's check are these equal now have we do we have what we need it's not

160

because uh two is less than three so we haven't met the condition yet

161

so we have to continue but notice how

162

that was an o of one operation we just had to make one comparison here

163

and then one comparison here we didn't have to go through the entire list

164

so now we're going to add an e

165

which we don't really care about now we're going to add a c

166

which we do care about

167

so let's update the length of this now are these exactly

168

equal we know we just met the condition for these last two now have we finally met our last condition

169

and yes they're both one so we can take this this two and replace it it's getting a little messy See.

170

but i hope you can see it so we have a three here

171

so now let's make the comparison between these two

172

and yes they are exactly equal so what

173

that tells us is this string contains we have exactly what we need right

174

so we met the condition this is a possible result

175

and i'm just going to take the two indices the start

176

and the ending of it which is zero and five and i'm going to put that as our current result.

177

So our current result is from zero to five.

178

And the length of that result happens to be six, right?

179

So now what are we going to do?

180

Are we just going to keep adding elements again and again?

181

Well, we want to find the minimum.

182

So let's at least try to find a string that's less than six.

183

So what are we going to do?

184

Let's remove the leftmost character and keep doing

185

that until this condition is no longer valid until we don't have what we need anymore

186

so we can try to at least find a smaller result

187

because ultimately we're looking for the minimum string

188

so i'm going to take this character and remove it from our current window

189

and so we're removing an a so what

190

that means is we have to update this

191

so it's no longer one we actually have a zero for count a now

192

and now we know

193

that this condition is this is less than what we need it to be

194

so this condition is no longer valid so

195

that also means we have to update this value

196

so before we had a three

197

but now we have to put a two we only have

198

two of these conditions met right these two characters b and c

199

so now we're actually just going to keep adding characters we're going to keep looking for the minimum

200

so we add an o but we know we don't care about

201

that we add a d we don't really care about

202

that we add an e we don't care about

203

that we add a b over here right we do care about b

204

so what are we gonna do we're gonna take the b

205

count it's one currently now we have two now that's great

206

because we actually have more than what we need right we we need one

207

but we have two so am i gonna take this

208

and update it no because they're not equal what

209

that means is we added an unnecessary character it's okay

210

but it didn't help satisfy the condition we already know this

211

and this were satisfied this is the one that needed to be satisfied

212

so since it's not exactly equal we're not going to increment our have count

213

so now let's add another character the a that we wanted

214

so badly so we added an a we update the count of a we add one

215

so now this is one we're gonna check are they exactly

216

equal have we met the condition now by adding a character did we make these exactly equal

217

and we did so what does that mean well we met one more condition

218

so we update our have count it's now going to be set to three

219

and now these are actually equal so we actually met we have exactly what we need so we potentially found a result.

220

Now the only problem is this result goes from index 1 all the way to roughly index 10

221

so it's actually bigger than our current result which is a problem.

222

So we don't update our result yet

223

but now we want to try to find an even smaller substring than this so let's start popping characters from the left.

224

So we pop a d but d's we don't care about

225

so we don't update our window

226

and let's just keep popping values until this condition is no longer met

227

so now let's pop a b

228

so let's now we have to update our value of b

229

so this was originally two now it's going to be set to one

230

so now it's set to one

231

so did we are did we undo this condition is this condition no longer valid nope

232

because this is still greater than or equal to the count

233

that we needed so the condition is still valid we don't have to update our have count yet

234

so actually this string is still a possible result

235

but notice this string goes from index 4 all the way to index 10

236

so it's actually length 7 and that's still greater than this string

237

so we cannot count this as a result yet

238

so now we remove the e and then we remove the c

239

so we have to actually update our count again

240

so this was originally one now it's going to be zero

241

and now you can see that this condition is actually no longer valid

242

so even though these two are still valid this one is not valid we have to update our have count

243

so our have count was three but now we removed one

244

so it's going to be two so now it's no longer equal so our string is no longer valid.

245

It's length five, but it doesn't have a C.

246

We have a B, we have an A, but we don't have a C.

247

so we can't update our result

248

so let's keep adding characters now maybe we'll find another valid string

249

so we add an n but we don't care about ends we add the c

250

that we want so we added a c

251

so we update our c count now it's set to one these are once again equal

252

so since they're exactly equal that means we just now have met the condition

253

so we met one more condition so we can update our have count now to three.

254

That means it's exactly equal to what it needs to be.

255

That means this is a valid string.

256

So this goes, this goes from index six all the way to index 12.

257

That's a length of seven, which is not smaller than our current result, but that doesn't mean we can't shrink this, right?

258

So let's start from the left and keep popping and making it smaller, but also keep going until it's no longer valid anymore.

259

So we pop an O.

260

Let's remove a D.

261

But we're still valid, right?

262

We didn't update any of these.

263

And now you see we have a string of length 5.

264

So we can actually update our result.

265

So now we're going from index 8 to index 12.

266

And that leaves us with a length of 5.

267

But we're not done yet.

268

We have an E.

269

We can remove that E as well.

270

Now you notice we're still valid we have a b we have an a

271

and we have a c we didn't have to update our

272

map our have count is exactly equal to the need

273

so now we can update our result one more time

274

and it's gonna go from index 9 all the way to

275

index 12 that's the string the length of it is four

276

and lastly we are gonna remove this b character from it as well

277

and once we remove the b you can see okay, we removed this one.

278

Now we have zero bees remaining.

279

That's less than how many we need.

280

So we have to update the have count.

281

So we set it to two.

282

The condition is no longer valid.

283

And so are we going to continue our algorithm?

284

Well, we have no more characters left to add.

285

We reached the end of the string.

286

So since this is our current minimum and our current result, this is what we're going to end up returning

287

and by the way we just solved this problem in big o of n time

288

because you see we added each character once that's an o

289

of one we removed each character once every time we added

290

or removed a character we did at most two operations right we had to update one spot in our map

291

and we had to potentially update this right okay

292

so now let's finally get into the code the first thing

293

i'm going to do is actually handle a edge case so

294

if the input string t which is you know our string is like the substring

295

that we're looking for

296

if it's empty then what i'm going to do is return an empty string

297

because that's just how they want us to handle it in this problem

298

and i'm going to have two windows that i showed previously

299

so count of t and just the current window

300

that we have they're both initially going to be hash maps they're both initially going to be empty

301

and the first thing i want to do is initialize our count t map

302

because we know this map actually isn't going to change at all

303

so for every character in string t i'm going to add one to it

304

but the value i'm going to get i can't just do this

305

because it's possible that c hasn't even been added to count t yet

306

so i'm going to do some python stuff i'm going to use the function get

307

which is good for this

308

so i'm going to get c i'm going to get the count of c

309

so if c exists in our map it will give me the value that's stored in here

310

if it doesn't exist i can put a default value

311

which is going to be zero so

312

if it doesn't exist this function will return zero

313

so that's just a way that i like to handle this case

314

so now that we've initialized the count of t we can have our variables have and need.

315

So we know have initially is going to be zero

316

because we have zero of the characters we need

317

and need is going to be initialized to the length of count t

318

because that length of count t gives us the unique characters in the string t.

319

And then I'm just going to start iterating through every character in s.

320

So I'm going to use a right pointer for

321

that the r is going to tell us the right boundary of our current window

322

so i'm going to get the character that we just reached

323

which is s at index r

324

so i'm just going to put it in a variable c

325

so with c we know we can update our current window

326

so i'm going to do window of c

327

and add one to it for the character that we just reached

328

and here i'm basically doing what i did above

329

if c has never been added to window we're just going to return zero with this function

330

so one plus zero we'll put a one here

331

if it does already exist this function will get us the count that was stored in here So we're updating our window, we're adding the count to it.

332

Now we want to know, does this count completely satisfy what we were looking for?

333

Does window of C equal exactly count of T?

334

That means we just satisfied a condition for the first time.

335

But one thing I also want to check before I check this is

336

that C is even a character in count T count t

337

so if c is in count t and this is true

338

because we know we don't actually care about the characters

339

that aren't even in the string t to begin with

340

and we know if this is true we can update our have count

341

so we can increment it by one this means we just satisfied a condition

342

so now what we want to know does have equal need exactly

343

so are they actually equal if that's true i'm going to run a loop

344

and i'm going to show you why it needs to be a loop

345

so if we actually met the condition let's one update our result potentially right

346

so if we found a new minimum result let's update

347

so this actually reminds me that i didn't even set a result

348

so let's set our result and our result length

349

so initially we know our result is going to be a pointer like a left

350

and right pointer so i'm just going to give it a default value of negative one negative one

351

and for the result length I'm going to put float infinity

352

because that's a good default value in this case

353

because we are looking for the minimum string

354

so any value will obviously be less than infinity

355

and I'm also going to initialize a left pointer

356

because we know r tells us the right pointer left pointer will initially be set to zero

357

but so now we can actually update our result we know the condition has been met

358

so if the current length of our string

359

which is going to be r minus left plus one this

360

is how you just calculate the size of our current window

361

if it happens to be less than the current result length

362

which initially starts at infinity so this will definitely execute at least once

363

if this is true we can update our result

364

which is stored over here So we can set our result to left and right.

365

This is the window.

366

And we can set our result length equal to the size of this window, which we just computed above.

367

But let's compute it again.

368

This is the size of the window.

369

And just like I showed you in the drawing, while the condition is met, we want to keep shrinking from the left.

370

We want to make this string as small as it can possibly be

371

so let's pop from the left of our window right let's try to minimize it

372

so i'm going to remove the leftmost character from our window map

373

so the leftmost character is is the string at index left right

374

and from this i'm going to decorum it by one

375

so now since we removed a character it's possible that our have

376

and need condition is no longer met

377

so i'm going to do something similar to what we did up here i'm gonna check

378

if this character s of l was in count t meaning it's one of the characters

379

that we need to satisfy our condition and

380

if somehow right now for the first time

381

that we took this character from our window

382

and now the count is actually less than the count

383

that we need which is present in count t so now

384

if it's if the

385

if by removing a character we just made it less than

386

what it needed to be what we did is we just took our have

387

and then decremented it by one right

388

so this is just a part of removing a character from

389

the left we update our map we update our have count

390

if we need to and lastly we take our left pointer

391

and increment it by one because of course we have to shift this by one

392

if we're removing our character from the left of our window

393

so now after we do this we're going to potentially check the have

394

and need condition and it might be true it might not be true

395

and whatever it is the loop is going to execute

396

when it needs to

397

so this is all we're doing we're taking characters adding it to our window map checking

398

if the condition has been met updating the window accordingly that's

399

all we need to do by the end the result

400

if it exists will be stored in our result variable

401

so our result pointer we can put it in left

402

and right we can take result and extract it into left

403

and right these these pointers in this case these new left

404

and rights will tell us the result

405

so what we can do is say return from string s

406

going from pointer left all the way to pointer right

407

but we need to add one for the off by one error

408

and we're only going to do this

409

if the result length has not has been changed meaning it's no longer infinity

410

because we know it's actually possible that a result does not even exist.

411

If that's not true, if a result doesn't exist, we know we have to return an empty string.

412

So there it is.

413

This is the entire code.

414

I'll probably have to link this in the description

415

because it's pretty long and even kind of messy and you can see it is definitely very efficient.

416

This is a linear time algorithm.

417

So I really hope that this was helpful.

418

If it was, please like and subscribe.

419

It supports the channel a lot and hopefully I'll see you pretty soon.

📺 Mesmo canal

Two Sum - Leetcode 1 - HashMap - Python

University StudentsBusiness English+1

The BEST Coding Interview Roadmap in 2023 (free)

University StudentsBusiness English+2

✨ Vídeo recomendado

52 frases

O que é a Técnica de Shadowing?

Shadowing é uma técnica de aprendizado de idiomas com base científica, originalmente desenvolvida para o treinamento de intérpretes profissionais. O método é simples, mas poderoso: você ouve áudio em inglês nativo e repete imediatamente em voz alta — como uma sombra seguindo o falante com 1-2 segundos de atraso. Pesquisas mostram melhora significativa na precisão da pronúncia, entonação, ritmo, sons conectados, compreensão auditiva e fluência na fala.

Técnica de shadowing: leia o guia completo passo a passo →

Prática de Shadowing: Minimum Window Substring - Airbnb Interview Question - Leetcode 76 - Aprenda a falar inglês com vídeo

I don't like Programming

Two Sum - Leetcode 1 - HashMap - Python

The BEST Coding Interview Roadmap in 2023 (free)

MiniMax 2026 06 09 06 47 09 Captivating Female

[Practice Problems] Regular Expressions (Regex) - Visually Explained

Natural Language Processing - Tokenization (NLP Zero to Hero - Part 1)

B2 Shadowing Practice Missing A Connection At The Airport

8 New CSS, JS and HTML Features You Should Know

We Let $200 GPT-Pro Think for 7 Days on Unsolved Math

Concurrency in Low-level Design Interviews w/ Staff Engineer

Array Map in 100 Seconds

Kth Smallest element in a matrix | Leetcode #378

Netflix product manager mock interview and tips (with ex-Netflix Lead PM)

8 Tech Choices to Lock In Before Agentmaxxing

O que você vai aprender

Ouvir atentamente esses sons

Fale como um nativo

O que é a Técnica de Shadowing?