Can you please tell me the test cases which got failed.
Please tell me the test case not passed
For the test case:
226 897 4
10724 96288 65641 70350 50894 2045 17684 65108 58455 84844 13804 29855 30699 77215 82270 69897 78171 26822 64745 42283 59310 15515 79421 42393 35405 20894 10516 85440 98613 59808 1689 66299 71376 60083 8488 22285 746 7592 65448 3282 48433 29390 27737 44130 66831 88837 58294 31441 26160 37003 72122 83985 98025 86573 84185 80399 64244 29252 66688 6009 75413 21751 26870 54277 65057 94886 33717 4018 1266 43082 63665 77864 84951 80609 63810 41489 24225 52386 94080 83669 73451 30200 18195 66711 85972 8349 99969 30964 37342 4806 85461 33224 32964 61601 9447 49283 56234 62412 57191 38924 12832 5896 61566 96636 40699 75291 42699 48050 81187 3044 3824 92436 42648 40496 53551 7668 20953 15867 85696 59166 67944 93707 95710 88430 66261 97419 51704 74777 45389 77539 91325 67555 26869 98774 36441 36635 72655 69925 87517 85234 41182 28231 13767 18750 90589 45046 20962 51938 70772 7801 17803 15906 54855 78194 53201 40243 29206 24126 60530 55726 14144 11239 44159 46420 65506 66450 75607 48981 31777 21880 6975 80461 45151 12879 98700 6082 1726 81102 1616 32333 90448 13361 69752 11976 18760 34854 22828 82100 2866 72184 45568 34199 15911 90783 11403 88037 81554 26609 89701 59426 51456 78243 87857 66861 6878 63470 57778 56500 26751 35252 43706 58327 46934 53258 50418 31500 52783 8311 26545 8672 75883 69583 3223 5642 73658 10438
170 35094 96417 39015 27590 70922 86361 3861 84523 22578 27388 77273 57155 56840 59904 33658 11108 57184 4160 98428 2330 21795 68861 35135 28953 76853 30345 97044 73488 4604 93072 91692 66576 55604 97759 88431 57489 72860 58201 37049 72532 37509 36568 60417 1817 491 55562 83849 14884 25916 26694 77376 36715 29233 49320 97717 83556 57427 93713 31611 74856 94326 83396 83208 35830 58893 13615 51828 4456 18166 44699 83942 4609 87884 80055 55516 93552 29587 16167 17669 59162 46854 97181 72480 77346 6693 5101 21048 3960 5342 22864 25760 91304 56958 2646 43821 21931 34889 89381 25514 80711 69001 14806 52872 29278 43914 6382 53649 94575 37920 19067 58784 8379 71309 73550 53805 76614 99079 64527 5928 6441 33425 70921 25700 54868 38084 83905 10231 83440 18005 9922 40695 88114 18768 4782 27859 59518 68687 43912 90167 76918 85880 2705 9721 48694 83432 37544 34096 82088 41982 95143 31349 91592 77943 98151 35333 59147 26710 60074 65816 65786 96943 54136 80571 25430 9892 10362 46052 18576 80913 90724 23949 63347 46716 58302 98036 71589 95319 17259 85772 73759 38285 96839 82618 70009 50132 81430 27100 53434 44218 71132 77702 78654 6271 11636 33497 21570 66490 89776 45709 38761 18663 17002 62891 87420 99183 78831 79895 43630 53789 21860 51101 3844 44350 71334 56525 78874 56095 42893 29928 92763 67210 24342 89235 14856 94937 55803 71085 85675 93711 39626 7459 81709 68485 74516 16302 46955 20055 30222 34953 77970 36537 40527 18482 32144 94645 40964 71161 19106 12503 34327 50915 63823 44843 22011 21939 86694 4918 15849 75888 9297 27035 86860 92226 3151 38469 55937 43405 83717 47341 40263 98792 42753 5096 30542 10902 45834 51330 8787 57244 98038 24921 72140 14052 63774 61870 74750 95845 45826 13700 78451 34092 61242 35156 98378 99153 62959 34949 22159 70298 51538 51671 60153 11927 55657 90332 62491 71313 47645 65223 27933 14436 8839 89196 73728 63524 20 94677 34615 88236 24339 28941 8196 8429 6587 17067 15359 30993 43409 37430 98068 71321 33386 52396 64782 50448 81245 40020 82498 73362 70449 22254 92867 2032 19179 15674 33710 70451 38509 12273 33688 31776 22976 88471 46103 68556 99496 5847 79227 14858 43865 70431 43461 70431 90178 48415 67850 17690 96492 68770 38249 78314 66164 11786 98986 70781 80938 38238 51287 43719 96187 84782 7600 29511 6900 60761 90893 7544 85606 77479 91151 3781 30516 38037 7046 87498 41561 114 58580 4194 25760 65670 32795 91711 84746 83246 83984 5995 67137 86204 83771 38055 71436 3466 97298 28312 40273 80745 13768 76093 4013 96885 90463 29167 16833 49702 88157 25916 10817 40702 53113 96335 54570 66175 83861 52702 92828 62120 61821 12868 86564 38993 41424 14285 70812 36855 1096 98460 15724 50430 23015 59514 20668 11426 33043 3290 91973 88327 37200 85534 7410 63926 5408 14773 35232 66673 56413 87299 62137 62400 77456 58986 39012 43219 10994 43048 60310 5200 73539 92770 94736 6782 70162 38012 69139 58502 37536 17536 67441 74893 9829 37026 33706 7611 57089 75252 71054 19222 6631 48887 68849 712 38814 82289 16612 52186 85210 88890 53521 53014 13840 11987 91795 13714 60303 8395 48042 94623 18350 30660 83941 82031 95580 78980 30381 7003 7691 11924 52685 87098 97106 36459 22613 76258 26639 99109 2032 44968 31938 47495 17107 88108 23995 29412 13333 59819 85617 56329 9532 19374 70849 70296 98080 35425 84452 20781 39405 13966 16426 70396 97244 45723 32612 59292 99065 87636 9674 39249 84402 65617 81589 23659 61656 73321 4938 96904 43008 68458 83927 73398 4051 37185 85852 25126 63933 71419 91009 47250 94019 30349 83904 86575 53186 32834 88737 61163 43597 98548 47013 89311 22032 15030 85942 39298 10011 27981 99239 88085 92013 97615 69630 87465 58633 47897 10438 82037 41319 92570 97611 66845 70836 95785 87809 49650 71006 36836 67351 60502 34976 56818 73632 88814 61323 49361 22850 93188 82728 39332 4028 68089 18501 49475 203 12425 16002 12361 63960 64380 87920 91470 49662 44336 43616 57300 2115 77657 17560 46642 32340 8343 55593 70366 91746 7908 97493 25395 94033 39502 83982 34041 245 27169 75171 25632 37506 83682 39334 87819 75658 42958 3347 2182 85629 33265 80606 38944 19263 69402 6559 95962 90588 82563 11495 41085 67013 87725 17533 73585 17958 96048 64282 8637 48467 56384 25745 62449 59078 738 69198 70803 34465 56774 81523 61115 59516 34448 36723 77748 86623 24640 95392 6983 39893 86753 22537 18160 11287 58143 52894 54012 73211 11728 99131 1017 74898 61854 21821 27037 27336 67116 29589 43401 69236 95633 52619 50087 57823 16738 97667 22094 9223 57176 25573 21138 59951 40076 41431 582 34489 79779 2808 85244 23107 17576 73107 14604 86897 9692 28295 23970 73562 76320 21482 51668 71485 64484 63928 88493 55794 39938 48953 44098 89924 33062 59681 11026 96049 40486 44864 97933 46011 90285 1138 30781 88881 95117 87540 66148 9052 70926 38380 70240 40215 95190 67678 50333 38824 94336 45326 47138 23288 36123 51196 78165 68360 87811 36650 61458 99011 24140 66216 15787 22046 54858 82747 18440 90922 62213 86094 6735 71734 53630 67346 75990 17488 78770 21920 5053 84994 675 91909 69182 55374 13269 94680 77050 68715 14584 18864 34429 18912 79890 34082 17836 53905 41097 89719 22640 69384 40072 42215 83300 50673 36308 9177 27100 64851 86677 86263 14282 92736 95606 12433 32954 7202 11104 38561 49069 91268 27448 52769 65209 1051 43935 13264 91543 78186 35697 51521 55936 34458 80992 67874 73879 44952 43353 47942
correct answer should be 5
input:
2 118 5
2707 14357
89456 80893 97510 22004 97863 99591 63099 63118 97619 69707 83128 24976 11966 2989 30681 61807 41417 45083 81927 68383 34204 5172 54346 21631 78259 31347 91642 72869 5529 97819 33179 5843 59032 72174 86698 31567 31549 82460 54252 30509 8618 5143 33794 19639 85056 96866 7251 35233 17891 99383 14352 78611 35184 41275 72038 92913 62773 42175 12862 45793 60507 50711 53008 10230 1485 40619 96591 27773 23461 2104 63244 75361 88606 19295 93015 18022 22788 24480 38063 48782 12731 31331 80888 22006 22779 10367 81357 70939 79289 89549 83862 50514 1901 99294 4663 11519 5428 63451 23786 47163 39730 53542 77737 41896 86725 19371 47682 32341 72470 1615 43311 14390 79329 50348 72173 17301 81704 56732
output:
2
Maam I have been tought the same code , using strings in my video tutorial . Can you please tell where my code is getting failed and what correction I should do.
As mentioned in the problem statement, given problem is quite similar to the standard LCS problem. We can have following dp state DP(n,m,k) = denotes LCS for first n number of first array, first m numbers of second array when we are allowed to change at max k numbers in first array.
Recursion look like this ->
DP(n,m,k) = max(DP(n-1,m,k), DP(n, m-1, k), DP(n-1, m-1, k-1)+1), if arr[n]!=arr[m]
DP(n,m,k) = max(DP(n-1,m,k), DP(n, m-1, k), DP(n-1, m-1, k)+1), if arr[n]==arr[m]
The total number of distinct states, hence are = n * m * k
Time complexity = O(n * m * k)
see this:
public static long korderedLCS(int[] a, int[] b, int i, int j, int k, long[][][] dp) {
if (a.length == i || b.length == j) {
return 0;
}
if (dp[i][j][k] != -1) {
return dp[i][j][k];
}
long res = 0;
if (a[i] == b[j]) {
res = 1 + korderedLCS(a, b, i + 1, j + 1, k, dp);
} else {
if (k > 0) {
res = 1 + korderedLCS(a, b, i + 1, j + 1, k - 1, dp);
}
res = Math.max(res, korderedLCS(a, b, i + 1, j, k, dp));
res = Math.max(res, korderedLCS(a, b, i, j + 1, k, dp));
}
dp[i][j][k] = res;
return res;
}