Commitbd6fb0b

committed

Create: 76-Minimum-Window-Substring.ts

1 parentfda9a29 commitbd6fb0bCopy full SHA for bd6fb0b

File tree

+48

-0

lines changed

+48

-0

lines changed

Lines changed: 48 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,48 @@`
	`1`	`+functionminWindow(s:string,t:string):string{`
	`2`	`+letminL=0;`
	`3`	`+letminR=s.length;`
	`4`	`+`
	`5`	`+//create string t hashmap and needed`
	`6`	`+consttCount={};`
	`7`	`+letneeded=0;`
	`8`	`+for(leti=0;i<t.length;i++){`
	`9`	`+if(t[i]intCount)tCount[t[i]]++;`
	`10`	`+else{`
	`11`	`+tCount[t[i]]=1;`
	`12`	`+needed++;`
	`13`	`+}`
	`14`	`+}`
	`15`	`+`
	`16`	`+//initialize winCount(empty)`
	`17`	`+constwinCount={};`
	`18`	`+letmatched=0;`
	`19`	`+`
	`20`	`+letl=0;`
	`21`	`+`
	`22`	`+for(letr=0;r<s.length;r++){`
	`23`	`+//update winCount with adding s[r]`
	`24`	`+if(s[r]inwinCount)winCount[s[r]]++;`
	`25`	`+elsewinCount[s[r]]=1;`
	`26`	`+//update matched`
	`27`	`+if(s[r]intCount&&winCount[s[r]]===tCount[s[r]])matched++;`
	`28`	`+`
	`29`	`+//the window is valid`
	`30`	`+while(matched===needed){`
	`31`	`+//update min`
	`32`	`+if(r-l+1<minR-minL+1){`
	`33`	`+minL=l;`
	`34`	`+minR=r;`
	`35`	`+}`
	`36`	`+`
	`37`	`+//remove l`
	`38`	`+//update matched`
	`39`	`+if(s[l]intCount&&winCount[s[l]]===tCount[s[l]])matched--;`
	`40`	`+//update winCount with the removal of s[l]`
	`41`	`+winCount[s[l]]--;`
	`42`	`+if(winCount[s[l]]===0)deletewinCount[s[l]];`
	`43`	`+l++;`
	`44`	`+}`
	`45`	`+}`
	`46`	`+`
	`47`	`+returnminR-minL+1>s.length ?'' :s.slice(minL,minR+1);`
	`48`	`+}`

Comments

(0)