Commit1424689

authored

Create maximum-number-of-subsequences-after-one-inserting.py

1 parenta592f2c commit1424689Copy full SHA for 1424689

File tree

+26

-0

lines changed

+26

-0

lines changed

Lines changed: 26 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,26 @@`
	`1`	`+# Time: O(n)`
	`2`	`+# Space: O(1)`
	`3`	`+`
	`4`	`+# prefix sum, dp`
	`5`	`+classSolution(object):`
	`6`	`+defnumOfSubsequences(self,s):`
	`7`	`+"""`
	`8`	`+ :type s: str`
	`9`	`+ :rtype: int`
	`10`	`+ """`
	`11`	`+cnt_l=cnt_c=0`
	`12`	`+cnt_t=s.count('T')`
	`13`	`+mx_cnt_lt=cnt_lct=cnt_lc=cnt_ct=0`
	`14`	`+forxins:`
	`15`	`+mx_cnt_lt=max(mx_cnt_lt,cnt_l*cnt_t)`
	`16`	`+ifx=='L':`
	`17`	`+cnt_l+=1`
	`18`	`+elifx=='C':`
	`19`	`+cnt_c+=1`
	`20`	`+cnt_lc+=cnt_l`
	`21`	`+elifx=='T':`
	`22`	`+cnt_t-=1`
	`23`	`+cnt_ct+=cnt_c`
	`24`	`+cnt_lct+=cnt_lc`
	`25`	`+mx=max(mx_cnt_lt,cnt_l*cnt_t)`
	`26`	`+returncnt_lct+max(cnt_ct,mx_cnt_lt,cnt_lc)`

Comments

(0)