The general longest common subsequence problem (LCS) over a binary alphabet is NP-complete. Does the problem remain NP-complete if each input string has m zeros and n ones, where m and n are constants?I asked this question on cs.stackexchange and was told, The problem probably remains NP-complete. However, I was unsuccessful in showing a reduction from the original LCS problem.
Is longest common subsequence with bounded occurrences NP-complete?
cc.complexity theory;np hardness
This paper by Blin et al. (Hardness of Longest Common Subsequence for Sequences with Bounded Run-Lengths, CPM'12) provides a reduction from independent set to LCS where the Hamming weights of all strings are the same (it is $n-1$ where $n$ is the number of vertices in the independent set instance). Thus, the problem remains NP-complete under this assumption.