Commita592f2c

authored

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

1 parent924e411 commita592f2cCopy full SHA for a592f2c

File tree

+27

-0

lines changed

+27

-0

lines changed

Lines changed: 27 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,27 @@`
	`1`	`+// Time: O(n)`
	`2`	`+// Space: O(1)`
	`3`	`+`
	`4`	`+// prefix sum, dp`
	`5`	`+classSolution {`
	`6`	`+public:`
	`7`	`+longlongnumOfSubsequences(string s) {`
	`8`	`+int64_t cnt_l =0, cnt_c =0;`
	`9`	`+int64_tcnt_t =count(cbegin(s),cend(s),'T');`
	`10`	`+int64_t mx_cnt_lt =0, cnt_lct =0, cnt_lc =0, cnt_ct =0;`
	`11`	`+for (constauto& x : s) {`
	`12`	`+ mx_cnt_lt =max(mx_cnt_lt, cnt_l *cnt_t);`
	`13`	`+if (x =='L') {`
	`14`	`+ ++cnt_l;`
	`15`	`+ }elseif (x =='C') {`
	`16`	`+ ++cnt_c;`
	`17`	`+ cnt_lc += cnt_l;`
	`18`	`+ }elseif (x =='T') {`
	`19`	`+ --cnt_t;`
	`20`	`+ cnt_ct += cnt_c;`
	`21`	`+ cnt_lct += cnt_lc;`
	`22`	`+ }`
	`23`	`+ }`
	`24`	`+ mx_cnt_lt =max(mx_cnt_lt, cnt_l *cnt_t);`
	`25`	`+return cnt_lct +max({cnt_ct, mx_cnt_lt, cnt_lc});`
	`26`	`+ }`
	`27`	`+};`

Comments

(0)