FPEvalDataset/LeetCodeProblem
0305
1{2 "id": 3713,3 "name": "frequencies_of_shortest_supersequences",4 "difficulty": "Hard",5 "link": "https://leetcode.com/problems/frequencies-of-shortest-supersequences/",6 "date": "2025-01-19 00:00:00",7 "task_description": "You are given an array of strings `words`. Find all **shortest common supersequences (SCS)** of `words` that are not permutations of each other. A **shortest common supersequence** is a string of **minimum** length that contains each string in `words` as a subsequence. Return a 2D array of integers `freqs` that represent all the SCSs. Each `freqs[i]` is an array of size 26, representing the frequency of each letter in the lowercase English alphabet for a single SCS. You may return the frequency arrays in any order. **Example 1:** **Input:** words = [\"ab\",\"ba\"] **Output: **[[1,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[2,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]] **Explanation:** The two SCSs are `\"aba\"` and `\"bab\"`. The output is the letter frequencies for each one. **Example 2:** **Input:** words = [\"aa\",\"ac\"] **Output: **[[2,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]] **Explanation:** The two SCSs are `\"aac\"` and `\"aca\"`. Since they are permutations of each other, keep only `\"aac\"`. **Example 3:** **Input:** words = [\"aa\",\"bb\",\"cc\"] **Output: **[[2,2,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]] **Explanation:** `\"aabbcc\"` and all its permutations are SCSs. **Constraints:** `1 <= words.length <= 256` `words[i].length == 2` All strings in `words` will altogether be composed of no more than 16 unique lowercase letters. All strings in `words` are unique.",8 "public_test_cases": [9 {10 "label": "Example 1",11 "input": "words = [\"ab\",\"ba\"]",12 "output": "[[1,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[2,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]] "13 },14 {15 "label": "Example 2",16 "input": "words = [\"aa\",\"ac\"]",17 "output": "[[2,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]] "18 },19 {20 "label": "Example 3",21 "input": "words = [\"aa\",\"bb\",\"cc\"]",22 "output": "[[2,2,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]] "23 }24 ],25 "private_test_cases": [26 {27 "input": [28 "\"wp\"",29 "\"gb\"",30 "\"mv\"",31 "\"ng\"",32 "\"em\"",33 "\"ls\"",34 "\"ay\"",35 "\"ah\"",36 "\"xt\"",37 "\"ua\"",38 "\"pn\"",39 "\"mg\"",40 "\"fs\"",41 "\"pq\"",42 "\"kp\"",43 "\"ja\"",44 "\"hs\"",45 "\"au\"",46 "\"wh\"",47 "\"tc\"",48 "\"cm\"",49 "\"ku\"",50 "\"zb\"",51 "\"cz\"",52 "\"sm\"",53 "\"bk\"",54 "\"nu\"",55 "\"wu\"",56 "\"su\"",57 "\"yh\"",58 "\"rv\"",59 "\"oz\"",60 "\"ce\"",61 "\"br\"",62 "\"fy\"",63 "\"jq\"",64 "\"qg\"",65 "\"qr\"",66 "\"zz\"",67 "\"xi\"",68 "\"ov\"",69 "\"ib\"",70 "\"ci\"",71 "\"cq\"",72 "\"gm\"",73 "\"vt\"",74 "\"gq\"",75 "\"lx\"",76 "\"hz\"",77 "\"qw\"",78 "\"pp\"",79 "\"oo\"",80 "\"xv\"",81 "\"ey\"",82 "\"gc\"",83 "\"sa\"",84 "\"fw\"",85 "\"dx\"",86 "\"zv\"",87 "\"ni\"",88 "\"gr\"",89 "\"kd\"",90 "\"wg\"",91 "\"yy\"",92 "\"gl\"",93 "\"wy\"",94 "\"sn\"",95 "\"bn\"",96 "\"kn\"",97 "\"qp\"",98 "\"vg\"",99 "\"rb\"",100 "\"hh\"",101 "\"nz\"",102 "\"jx\"",103 "\"mu\"",104 "\"xu\"",105 "\"mn\"",106 "\"hy\"",107 "\"mr\"",108 "\"ev\"",109 "\"qa\"",110 "\"me\"",111 "\"sq\"",112 "\"dg\"",113 "\"qu\"",114 "\"iy\"",115 "\"od\"",116 "\"sf\"",117 "\"jf\"",118 "\"tt\"",119 "\"ym\"",120 "\"ki\"",121 "\"wi\"",122 "\"ts\"",123 "\"ur\"",124 "\"du\"",125 "\"dd\"",126 "\"dq\"",127 "\"ie\"",128 "\"zg\"",129 "\"wc\"",130 "\"bj\"",131 "\"xf\"",132 "\"md\"",133 "\"ac\"",134 "\"sx\"",135 "\"ra\"",136 "\"my\"",137 "\"rd\"",138 "\"fq\"",139 "\"vy\"",140 "\"bi\"",141 "\"fn\"",142 "\"ew\"",143 "\"rf\"",144 "\"fu\"",145 "\"za\"",146 "\"rr\"",147 "\"py\"",148 "\"iz\"",149 "\"kk\"",150 "\"pw\"",151 "\"rt\"",152 "\"ff\"",153 "\"tw\"",154 "\"fe\"",155 "\"lj\"",156 "\"bd\"",157 "\"fz\"",158 "\"re\"",159 "\"mb\"",160 "\"th\"",161 "\"et\"",162 "\"zl\"",163 "\"uz\"",164 "\"qh\"",165 "\"be\"",166 "\"kx\"",167 "\"dj\"",168 "\"jm\"",169 "\"ga\"",170 "\"zn\"",171 "\"bh\"",172 "\"vq\"",173 "\"wn\"",174 "\"qn\"",175 "\"np\"",176 "\"cb\"",177 "\"wl\"",178 "\"ll\"",179 "\"st\"",180 "\"vl\"",181 "\"vd\"",182 "\"tq\"",183 "\"no\"",184 "\"lp\"",185 "\"ho\"",186 "\"nt\"",187 "\"wv\"",188 "\"lz\"",189 "\"ys\"",190 "\"qe\"",191 "\"vh\"",192 "\"ge\"",193 "\"dm\"",194 "\"mz\"",195 "\"uo\"",196 "\"lt\"",197 "\"hv\"",198 "\"kh\"",199 "\"jr\"",200 "\"db\"",201 "\"nh\"",202 "\"pg\"",203 "\"qv\"",204 "\"qf\"",205 "\"vp\"",206 "\"va\"",207 "\"xm\"",208 "\"ry\"",209 "\"to\"",210 "\"li\"",211 "\"sk\"",212 "\"lq\"",213 "\"bt\"",214 "\"al\"",215 "\"we\"",216 "\"fb\"",217 "\"ea\"",218 "\"wd\"",219 "\"up\"",220 "\"az\"",221 "\"vn\"",222 "\"hc\"",223 "\"ui\"",224 "\"tp\"",225 "\"ql\"",226 "\"hg\"",227 "\"lk\"",228 "\"tm\"",229 "\"pi\"",230 "\"zs\"",231 "\"aj\"",232 "\"tl\"",233 "\"td\"",234 "\"kq\"",235 "\"sr\"",236 "\"so\"",237 "\"ou\"",238 "\"gi\"",239 "\"tn\"",240 "\"ha\"",241 "\"yp\"",242 "\"rs\"",243 "\"dp\"",244 "\"pl\"",245 "\"ub\"",246 "\"ot\"",247 "\"na\"",248 "\"oj\"",249 "\"nn\"",250 "\"lm\"",251 "\"xd\"",252 "\"cv\"",253 "\"en\"",254 "\"pd\""255 ],256 "output": [257 [258 2,259 2,260 1,261 2,262 2,263 2,264 2,265 2,266 1,267 1,268 2,269 2,270 1,271 2,272 2,273 2,274 2,275 2,276 1,277 2,278 1,279 1,280 1,281 1,282 2,283 2284 ]285 ]286 },287 {288 "input": [289 "\"kj\"",290 "\"kn\"",291 "\"eb\"",292 "\"vo\"",293 "\"hg\"",294 "\"jn\"",295 "\"qd\"",296 "\"ye\"",297 "\"ai\"",298 "\"ux\"",299 "\"cg\"",300 "\"lh\"",301 "\"qg\"",302 "\"ls\"",303 "\"lf\"",304 "\"wd\"",305 "\"pf\""306 ],307 "output": [308 [309 1,310 1,311 1,312 1,313 1,314 1,315 1,316 1,317 1,318 1,319 1,320 1,321 0,322 1,323 1,324 1,325 1,326 0,327 1,328 0,329 1,330 1,331 1,332 1,333 1,334 0335 ]336 ]337 },338 {339 "input": [340 "\"jv\"",341 "\"vx\"",342 "\"jo\"",343 "\"wf\"",344 "\"uo\"",345 "\"gb\"",346 "\"zt\"",347 "\"db\"",348 "\"ko\"",349 "\"hu\"",350 "\"bc\"",351 "\"pq\"",352 "\"eb\"",353 "\"sj\"",354 "\"se\"",355 "\"bt\"",356 "\"wa\"",357 "\"mw\"",358 "\"xo\"",359 "\"qx\"",360 "\"da\"",361 "\"wz\"",362 "\"ok\"",363 "\"ts\"",364 "\"dh\"",365 "\"sb\"",366 "\"du\"",367 "\"yp\"",368 "\"dp\"",369 "\"ub\"",370 "\"gs\"",371 "\"bm\""372 ],373 "output": [374 [375 1,376 2,377 1,378 1,379 1,380 1,381 1,382 1,383 0,384 1,385 1,386 0,387 1,388 0,389 2,390 1,391 1,392 0,393 1,394 1,395 1,396 1,397 1,398 1,399 1,400 1401 ],402 [403 1,404 1,405 1,406 1,407 1,408 1,409 1,410 1,411 0,412 1,413 1,414 0,415 1,416 0,417 2,418 1,419 1,420 0,421 1,422 2,423 1,424 1,425 1,426 1,427 1,428 1429 ],430 [431 1,432 2,433 1,434 1,435 1,436 1,437 1,438 1,439 0,440 1,441 2,442 0,443 1,444 0,445 1,446 1,447 1,448 0,449 1,450 1,451 1,452 1,453 1,454 1,455 1,456 1457 ],458 [459 1,460 1,461 1,462 1,463 1,464 1,465 1,466 1,467 0,468 1,469 2,470 0,471 1,472 0,473 1,474 1,475 1,476 0,477 1,478 2,479 1,480 1,481 1,482 1,483 1,484 1485 ],486 [487 1,488 1,489 1,490 1,491 1,492 1,493 1,494 1,495 0,496 1,497 1,498 0,499 1,500 0,501 2,502 1,503 1,504 0,505 2,506 1,507 1,508 1,509 1,510 1,511 1,512 1513 ],514 [515 1,516 1,517 1,518 1,519 1,520 1,521 1,522 1,523 0,524 1,525 2,526 0,527 1,528 0,529 1,530 1,531 1,532 0,533 2,534 1,535 1,536 1,537 1,538 1,539 1,540 1541 ]542 ]543 },544 {545 "input": [546 "\"sk\"",547 "\"fj\"",548 "\"km\"",549 "\"ql\"",550 "\"in\"",551 "\"ex\"",552 "\"zp\"",553 "\"px\"",554 "\"dn\"",555 "\"ej\"",556 "\"xg\"",557 "\"pp\"",558 "\"yx\"",559 "\"ay\"",560 "\"jz\""561 ],562 "output": [563 [564 1,565 0,566 0,567 1,568 1,569 1,570 1,571 0,572 1,573 1,574 1,575 1,576 1,577 1,578 0,579 2,580 1,581 0,582 1,583 0,584 0,585 0,586 0,587 1,588 1,589 1590 ]591 ]592 },593 {594 "input": [595 "\"ex\"",596 "\"ao\"",597 "\"ak\"",598 "\"dy\"",599 "\"gr\"",600 "\"rf\"",601 "\"mz\"",602 "\"rr\"",603 "\"ch\"",604 "\"iz\"",605 "\"ry\"",606 "\"xw\"",607 "\"ju\"",608 "\"pj\"",609 "\"rt\"",610 "\"di\"",611 "\"eg\"",612 "\"ox\"",613 "\"ja\"",614 "\"ct\"",615 "\"je\"",616 "\"fp\"",617 "\"ku\"",618 "\"ph\"",619 "\"nb\"",620 "\"gh\"",621 "\"az\"",622 "\"fg\"",623 "\"tg\"",624 "\"kc\"",625 "\"qa\"",626 "\"gn\"",627 "\"oq\"",628 "\"qs\"",629 "\"gg\"",630 "\"ej\"",631 "\"ce\"",632 "\"xl\"",633 "\"un\"",634 "\"av\"",635 "\"cf\"",636 "\"bq\"",637 "\"uj\"",638 "\"jq\"",639 "\"xj\"",640 "\"oa\"",641 "\"km\"",642 "\"zz\"",643 "\"uu\"",644 "\"hn\"",645 "\"wj\"",646 "\"bo\"",647 "\"df\"",648 "\"co\"",649 "\"zi\"",650 "\"cv\"",651 "\"dm\"",652 "\"rn\"",653 "\"an\""654 ],655 "output": [656 [657 2,658 1,659 1,660 1,661 2,662 1,663 2,664 1,665 1,666 1,667 1,668 1,669 1,670 1,671 1,672 1,673 1,674 2,675 1,676 1,677 2,678 1,679 1,680 1,681 1,682 2683 ],684 [685 2,686 1,687 1,688 1,689 1,690 1,691 2,692 1,693 1,694 2,695 1,696 1,697 1,698 1,699 1,700 1,701 1,702 2,703 1,704 1,705 2,706 1,707 1,708 1,709 1,710 2711 ]712 ]713 }714 ],715 "haskell_template": "supersequences :: [String] -> [[Int]]\nsupersequences words ",716 "ocaml_template": "let supersequences (words: string list) : int list list = ",717 "scala_template": "def supersequences(words: List[String]): List[List[Int]] = { \n \n}",718 "java_template": "class Solution {\n public List<List<Integer>> supersequences(String[] words) {\n \n }\n}",719 "python_template": "class Solution(object):\n def supersequences(self, words):\n \"\"\"\n :type words: List[str]\n :rtype: List[List[int]]\n \"\"\"\n "720}