Please provide some hint

#1

please help me in approaching this problem.

Please provide me some hints to solve this problem
#2

@kodivine0
The hint is:
Start from the 0th indexes of both the strings. If both the strings are equal at the certain index, then add 1 to the answer and move on to the state (i + 1) and (j + 1), where i and j point to the current indexes of the two strings. Else , if you still some character changes left, you can change a character and move to the state (i + 1) and (j + 1). Else if no changes are allowed because you have exhausted all or you still have some changes left, you can move to the states (i + 1, j) and (i, j + 1) and choose the maximum of the two as the answer.

If you face any difficulty during implementation, please feel free to revert.

#3

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.

#4

i could not understand ur explanation properly

#5

@kodivine0
This is a 3D dp problem. The initial state is the 0 index of both the strings. If at some time you are at state (i, j), if a[i] == b[j], you can add 1 to answer and move to state (i + 1, j + 1), else, if (k > 0), i.e, if you still some character changes left, you can change a character and move to the state (i + 1) and (j + 1). Else if no changes are allowed because you have exhausted all or you still have some changes left, you can move to the states (i + 1, j) and (i, j + 1) and choose the maximum of the two as the answer.

This is my code for the question :

If you face any issue in the implementation, feel free to revert.
If my answer was able to resolve your query, please mark the doubt as resolved.

#6

First simply find the length of the longest common subsequence of the two strings as it is. Now you can change atmost k elements from the first sequence to any character. So add k to it. If the resulting value is greater than the lengths of any of the strings, set it to the minimum length between the two strings.
And this will be your answer.

#7

why does a 2-d array not support more than 1000 elements?

#8

A 2d array can hold more than 1000 elements.

#9

ok, i got it now, where i was going wrong!

#10

Welcome. Please mark your doubt as resolved now.

#11

@S19APP-PP0108,
About the solution you suggest, in which k is added to the normal lcs answer for the tqo strings. The approach passes all the testcase in the submission, But i have a doubt.
can you help me with this test case according to that apporach?
the test case is as follows:
5 9 3
abcde
cdhjkiabk

I am getting ans = 5 according to the approach, but i believe ans = 3 should be correct for the same.

Can you please help me here?