package com.sunny.grokkingalgorithms.fasttrack.dynamicprogrammingandrecursion;

import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.Set;

/**
 * Created by sundas on 6/14/2018.
 */
public class LongestCommonSubsequence {

  /*
  Given two strings find count of the longest common subsequence
   */

  /**
   *
   * @param s1
   * @param s2
   * @return
   */
    public static int findLongestCommonSubsequence(String s1,
                                                   String s2){
      int maxCount = -1;
      int j = 0;
      for(int i = 0 ;i < s1.length() ; i++){
        int size = findSizeOfCommonSubsequence(s1,s2,i);
        if(size > maxCount){
          maxCount = size;
        }
      }
      return maxCount;
    }

  /**
   *
   * @param s1
   * @param s2
   * @param s1Begin
   * @return
   */
   public static int findSizeOfCommonSubsequence(String s1,String s2,
                                                 int s1Begin){
     int sizeOfSubsequence = 0;
     int s2Begin = 0;
     for(int i = s1Begin; i < s1.length() ; i++){
       for(int j = s2Begin; j < s2.length() ; j++){
         if(s1.charAt(i) == s2.charAt(j)){
           System.out.print(s1.charAt(i) + " ");
           sizeOfSubsequence++;
           s2Begin = j + 1;
         }
       }
     }
     System.out.println();
     return sizeOfSubsequence;
   }

  /**
   *
   * @param args
   */
  public static void main(String[] args) {
    String s1 = "ABCDGH";
    String s2 = "AEDFHR";
    //LCS = ADH
    System.out.println(findLongestCommonSubsequence(s1,s2));
    /*
    AGGTAB and GXTXAYB
     */
    s1 = "AGGTAB";
    s2 = "GXTXAYB";
    System.out.println(findLongestCommonSubsequence(s1,s2));
  }

}

@@ -315,16 +315,499 @@
 %0A   */%0A%0A
+  /**%0A   *%0A   * @param s1%0A   * @param s2%0A   * @return%0A   */%0A  public static int findLCSRecursive(String s1,%0A                                     String s2)%7B%0A    if(s1.length() == 0%0A        %7C%7C s2.length() == 0)%7B%0A      return 0;%0A    %7D%0A    if(s1.charAt(0)%0A        == s2.charAt(0))%7B%0A      return findLCSRecursive(s1.substring(1),s2.substring(1)) + 1;%0A    %7D%0A    else%7B%0A      return Math.max(findLCSRecursive(s1,s2.substring(1)),%0A          findLCSRecursive(s1.substring(1),s2));%0A    %7D%0A  %7D%0A%0A
   /**%0A  
@@ -912,32 +912,32 @@
 ence(String s1,%0A
-
                 
@@ -1650,24 +1650,26 @@
 %0A           
+//
 System.out.p
@@ -1782,24 +1782,26 @@
      %7D%0A     
+//
 System.out.p
@@ -2049,24 +2049,73 @@
 ce(s1,s2));%0A
+    System.out.println(findLCSRecursive(s1,s2));%0A
     /*%0A    A
@@ -2175,24 +2175,24 @@
  %22GXTXAYB%22;%0A
-
     System.o
@@ -2240,15 +2240,64 @@
 1,s2));%0A
+    System.out.println(findLCSRecursive(s1,s2));%0A
   %7D%0A%0A%7D%0A

Find LCS using recursion O(2.pow(n))