Nsryjdtyk

I've seen this today on a mock interview and wanted to give it a try. I'd love to hear some feedback from you guys. This is my second attempt at the problem, initially I had a mess of if/else towers and nested loops.

/*

 * Write a function that takes two strings s1 and s2 and returns the 

 * longest common subsequences of s1 and s2.

 *

 * Examples:  

 * s1: ABAZDC s2: BACBAD  result: ABAD  

 * s1: AGGTAB s2: GXTXAYB result: GTAB  

 * s1: aaaa   s2: aa      result: aa  

 * s1: aaaa   s2: ''      result: ''

 */

public class LongestSubsequence {



  public static void main(String args) {

    LongestSubsequence ls = new LongestSubsequence();



    assertEquals("ABAD", ls.solve("ABAZDC", "BACBAD"));

    assertEquals("GTAB", ls.solve("AGGTAB", "GXTXAYB"));

    assertEquals("aa", ls.solve("aaaa", "aa"));

    assertEquals("", ls.solve("aaaa", ""));

    assertEquals("ABAD", ls.solve("BACBAD", "ABAZDC"));

    assertEquals("aaaa", ls.solve("bcaaaa", "aaaabc"));

    assertEquals("aaaa", ls.solve("bcaaaade", "deaaaabc"));

  }



  private String solve(String s1, String s2) {

    if (s1.length() == 0 || s2.length() == 0) {

      return "";

    }



    String subSeq1 = getLongestSubsequence(s1, s2);

    String subSeq2 = getLongestSubsequence(s2, s1);

    return (subSeq1.length() >= subSeq2.length() ? subSeq1 : subSeq2);

  }



  private String getLongestSubsequence(String first, String second) {

    String retValue = "";

    int currentIndex = 0;

    for (int remaining = first.length(); retValue.length() < remaining; remaining--) {

      StringBuilder firstWorker = new StringBuilder(first.substring(currentIndex));

      StringBuilder secondWorker = new StringBuilder(second);

      StringBuilder possibleSequence = new StringBuilder();

      while (firstWorker.length() > 0 && secondWorker.length() > 0) {

        String ch = firstWorker.substring(0, 1);

        int firstIndex = secondWorker.indexOf(ch);

        if (firstIndex != -1) {

          possibleSequence.append(ch);

          secondWorker.delete(0, firstIndex + 1);

        }

        firstWorker.delete(0, 1);

      }

      if (possibleSequence.length() > retValue.length()) {

        retValue = possibleSequence.toString();

      }

      currentIndex++;

    }



    return retValue;    

  }



}

Bug

Your program fails on this test:

ls.solve("abddc", "acddb");

Your program finds "ab" and "ac" as the longest subsequences, but the actual answer should be "add".

The problem is that your algorithm is greedy, and it will always use any match, even if the match skips over a part that would produce a better answer. In my test case, the b in the first string matches the b at the end of the second string, thereby skipping over the dd in the middle.

The method name solve does not describe what the method is doing. There should be a method public static String longestCommonSubsequence(String a, String b), and the class containing that method should be called StringUtils.

After making the method static, there's no reason to call new LongestSubsequence any longer since that object doesn't provide anything useful.

The variable name ch is usually used for characters, not for strings. It creates unnecessary confusion here.