LCS of N strings

help
1

If I fix the 1st string and iterate for the 2nd string from 1 to < n and then I take the minimum size of LCS of all the iterations. Will this approach work?

2

It will not work.

A counter example for your approach:

3
ABC
A
B

Expected Output

0

Your Output

1

Also the following says the problem of finding LCS of N Strings is NP Hard.

2 Likes
3

Good solve :100::100:
what if it’s given that the size of all strings is same, in that case can I use that approach? Which I mentioned before.

4

Counter Example for modified Constraints:
Input

3
ABC
BBB
CCC

Expected Output

0

Your Output

1
1 Like
5

Thanks, your test cases made my doubts clear :100: