Given a string, find two identical subsequences with consecutive indexes C++

Question

I need to construct an algorithm (not necessarily effective) that given a string finds and prints two identical subsequences (by print I mean color for example). What more, the union of the sets of indexes of these two subsequences has to be a set of consecutive natural numbers (a full segment of integers).

In mathematics, the thing what I am looking for is called "tight twins", if it helps anything. (E.g., see the paper (PDF) here.)

Let me give a few examples:

1) consider string 231213231

It has two subsequences I am looking for in the form of "123". To see it better look at this image:

The first subsequence is marked with underlines and the second with overlines. As you can see they have all the properties I need.

2) consider string 12341234

3) consider string 12132344.

Now it gets more complicated:

4) consider string: 13412342

It is also not that easy:

I think that these examples explain well enough what I meant.

I've been thinking a long time about an algorithm that could do that but without success.

For coloring, I wanted to use this piece of code:

 using namespace std;
HANDLE  hConsole;
        hConsole = GetStdHandle(STD_OUTPUT_HANDLE);
    SetConsoleTextAttribute(hConsole, k);

where k is color.

Any help, even hints, would be highly appreciated.

Answer 1

Here's a simple recursion that tests for tight twins. When there's a duplicate, it splits the decision tree in case the duplicate is still part of the first twin. You'd have to run it on each substring of even length. Other optimizations for longer substrings could include hashing tests for char counts, as well as matching the non-duplicate portions of the candidate twins (characters that only appear twice in the whole substring).

Explanation of the function:

First, a hash is created with each character as key and the indexes it appears in as values. Then we traverse the hash: if a character count is odd, the function returns false; and indexes of characters with a count greater than 2 are added to a list of duplicates - characters half of which belong in one twin but we don't know which.

The basic rule of the recursion is to only increase i when a match for it is found later in the string, while maintaining a record of chosen matches (js) that i must skip without looking for a match. It works because if we find n/2 matches, in order, by the time j reaches the end, that's basically just another way of saying the string is composed of tight twins.

JavaScript code:

function isTightTwins(s){
  var n = s.length,
      char_idxs = {};

  for (var i=0; i<n; i++){
    if (char_idxs[s[i]] == undefined){
      char_idxs[s[i]] = [i];
    } else {
      char_idxs[s[i]].push(i);
    }
  }

  var duplicates = new Set();

  for (var i in char_idxs){

    // character with odd count
    if (char_idxs[i].length & 1){
      return false;
    }

    if (char_idxs[i].length > 2){
      for (let j of char_idxs[i]){
        duplicates.add(j);
      }      
    }
  }

  function f(i,j,js){

    // base case positive
    if (js.size == n/2 && j == n){
      return true;
    }

    // base case negative
    if (j > n || (n - j < n/2 - js.size)){
      return false;
    }

    // i is not less than j
    if (i >= j) {
      return f(i,j + 1,js);
    }

    // this i is in the list of js
    if (js.has(i)){
      return f(i + 1,j,js);

    // yet to find twin, no match
    } else if (s[i] != s[j]){
      return f(i,j + 1,js);

    } else { 

      // maybe it's a twin and maybe it's a duplicate
      if (duplicates.has(j)) {
        var _js = new Set(js);
        _js.add(j);
        return f(i,j + 1,js) | f(i + 1,j + 1,_js);          

      // it's a twin
      } else {
        js.add(j);
        return f(i + 1,j + 1,js);
      }
    }
  }

  return f(0,1,new Set());
}

console.log(isTightTwins("1213213515")); //  true
console.log(isTightTwins("11222332")); // false

Answer 2

WARNING: Commenter גלעד ברקן points out that this algorithm gives the wrong answer of 6 (higher than should be possible!) for the string 1213213515. My implementation gets the same wrong answer, so there seems to be a serious problem with this algorithm. I'll try to figure out what the problem is, but in the meantime DO NOT TRUST THIS ALGORITHM!

I've thought of a solution that will take O(n^3) time and O(n^2) space, which should be usable on strings of up to length 1000 or so. It's based on a tweak to the usual notion of longest common subsequences (LCS). For simplicity I'll describe how to find a minimal-length substring with the "tight twin" property that starts at position 1 in the input string, which I assume has length 2n; just run this algorithm 2n times, each time starting at the next position in the input string.

"Self-avoiding" common subsequences

If the length-2n input string S has the "tight twin" (TT) property, then it has a common subsequence with itself (or equivalently, two copies of S have a common subsequence) that:

• is of length n, and
• obeys the additional constraint that no character position in the first copy of S is ever matched with the same character position in the second copy.

In fact we can safely tighten the latter constraint to no character position in the first copy of S is ever matched to an equal or lower character position in the second copy, due to the fact that we will be looking for TT substrings in increasing order of length, and (as the bottom section shows) in any minimal-length TT substring, it's always possible to assign characters to the two subsequences A and B so that for any matched pair (i, j) of positions in the substring with i < j, the character at position i is assigned to A. Let's call such a common subsequence a self-avoiding common subsequence (SACS).

The key thing that makes efficient computation possible is that no SACS of a length-2n string can have more than n characters (since clearly you can't cram more than 2 sets of n characters into a length-2n string), so if such a length-n SACS exists then it must be of maximum possible length. So to determine whether S is TT or not, it suffices to look for a maximum-length SACS between S and itself, and check whether this in fact has length n.

Computation by dynamic programming

Let's define f(i, j) to be the length of the longest self-avoiding common subsequence of the length-i prefix of S with the length-j prefix of S. To actually compute f(i, j), we can use a small modification of the usual LCS dynamic programming formula:

f(0, _) = 0
f(_, 0) = 0
f(i>0, j>0) = max(f(i-1, j), f(i, j-1), m(i, j))
m(i, j) = (if S[i] == S[j] && i < j then 1 else 0) + f(i-1, j-1)

As you can see, the only difference is the additional condition && i < j. As with the usual LCS DP, computing it takes O(n^2) time, since the 2 arguments each range between 0 and n, and the computation required outside of recursive steps is O(1). (Actually we need only compute the "upper triangle" of this DP matrix, since every cell (i, j) below the diagonal will be dominated by the corresponding cell (j, i) above it -- though that doesn't alter the asymptotic complexity.)

To determine whether the length-2j prefix of the string is TT, we need the maximum value of f(i, 2j) over all 0 <= i <= 2n -- that is, the largest value in column 2j of the DP matrix. This maximum can be computed in O(1) time per DP cell by recording the maximum value seen so far and updating as necessary as each DP cell in the column is calculated. Proceeding in increasing order of j from j=1 to j=2n lets us fill out the DP matrix one column at a time, always treating shorter prefixes of S before longer ones, so that when processing column 2j we can safely assume that no shorter prefix is TT (since if there had been, we would have found it earlier and already terminated).