title: Number of Longest Common Subsequences
body: <p>I need to find the number of distinct longest common subsequences between two strings A and B. I am currently using the normal dynamic programming approach, and then generating all the distinct substrings by using a backtrack array and then doing a depth first search from the starting index.</p>
  
  <p>However, since the number of possible such answers is very high, my code is too slow. Is there any way to count the number of such distinct longest common subsequences without actually generating them ? </p>
  
  <p>My code so far: </p>
  
  <pre><code>import java.io.BufferedReader;
  import java.io.IOException;
  import java.io.InputStreamReader;
  import java.util.Arrays;
  import java.util.HashSet;
  import java.util.Iterator;
  import java.util.Stack;
  
  class Node
  {
  String res = "";
  int i;
  int j;
  
  public Node( int _i, int _j, String s )
  {
      i = _i;
      j = _j;
      res = s;
  }
  }
  
  public class LCSRevisited
  {
  static String a;
  static String b;
  static int m,n;
  static int[][] memo;
  static int[][] bt; // 1 means [i+1][j], 2 means [i][j+1], 3 means [i+1][j+1]
  // 4  - means both
  
  static HashSet &lt;String&gt; filter;
  
  static void printAllStrings( )
  {
      Iterator i = filter.iterator();
  
      while( i.hasNext())
      {
          System.out.println( i.next() );
      }
  } 
  
   static void printSol()
   {
     System.out.print( memo[ 0 ][ 0 ]);
  
     // check how many UNIQUE such strings exist
  
     filter = new HashSet();
     Stack&lt;Node&gt; s = new Stack();
     Node start = new Node( 0, 0, "" );
     s.push( start );
     Node curr;
     String res;
  
     // use backtrack array to do a DFS
  
     while( !s.isEmpty() )
     {
          curr = s.pop();
          res = curr.res;
  
          if( ( curr.i&gt;=m) || ( curr.j &gt;=n ) )
          {
              filter.add( curr.res);
              continue;
         }
  
          // check backtrack value
          int i = curr.i;
          int j = curr.j;
          int back = bt[ i ][ j];
  
          if( back == 1 )
          {
              s.push( new Node( i+1, j, res ));
          }
          if( back == 2 )
          {
              s.push( new Node( i, j+1, res ));
          }
          if( back == 3 )
          {
              s.push( new Node( i+1, j+1, res+a.charAt(i) ));
          }
          if( back == 4 )
          {
              s.push( new Node( i, j+1, res ));
              s.push( new Node( i+1, j, res ));
          }
     }
     //printAllStrings();
     System.out.println(" " + filter.size() );
  }
  
  static void solve()
  {
     // fill base cases
     m = a.length();
     n = b.length();
     memo = new int[ m+1 ][ n+1 ];
     Arrays.fill( memo[m], 0 );
  
     bt = new int[ m+1 ][ n+1 ];
  
     for( int i=0; i&lt;m; i++ )
     {
         memo[ i ][ n ] = 0;    
     }
  
     // Now compute memo values
     for( int i=m-1; i&gt;=0; i-- )
     {
         for( int j=n-1; j&gt;=0; j-- )
         {
             if( a.charAt(i) == b.charAt(j))
             {
                 memo[ i ][ j ] = 1 + memo[ i+1 ][ j+1 ];
                 bt[ i ][ j ] = 3;
             }
             else
             {
                 int r1 = memo[ i+1 ][ j ];
                 int r2 = memo[ i ][ j+1 ];
  
                 if( r1==r2 )
                 {
                      memo[ i ][ j ] = r1;
                      bt[ i ][ j ] = 4;
                 }
                 else if( r1 &gt; r2 )
                 {
                     memo[ i ][ j ] = r1;
                     bt[ i ][ j ] = 1;
                 }
                 else
                 {
                     memo[ i ][ j ] = r2;
                     bt[ i ][ j ] = 2;
                 }
             }
         }
     }
  
     printSol();
   }
  
  public static void main( String[] args ) throws IOException
  {
   BufferedReader br = new BufferedReader( new InputStreamReader( System.in ));
  
  int T= Integer.parseInt( br.readLine() );
  
  while( T--&gt; 0 )
  {
      a = br.readLine();
      b = br.readLine();
  
      if( T&gt;=1 )
      br.readLine();
  
      solve();
      // printArr( bt );
  }
  }
  }
  </code></pre>