Longest common subsequence solution 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() &gt;= subSeq2.length() ? subSeq1 : subSeq2);
  }

  private String getLongestSubsequence(String first, String second) {
    String retValue = "";
    int currentIndex = 0;
    for (int remaining = first.length(); retValue.length() &lt; remaining; remaining--) {
      StringBuilder firstWorker = new StringBuilder(first.substring(currentIndex));
      StringBuilder secondWorker = new StringBuilder(second);
      StringBuilder possibleSequence = new StringBuilder();
      while (firstWorker.length() &gt; 0 &amp;&amp; secondWorker.length() &gt; 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() &gt; retValue.length()) {
        retValue = possibleSequence.toString();
      }
      currentIndex++;
    }

    return retValue;    
  }

}
Bug
Your program fails on this test:
ls.solve(&quot;abddc&quot;, &quot;acddb&quot;);

Your program finds &quot;ab&quot; and &quot;ac&quot; as the longest subsequences, but the actual answer should be &quot;add&quot;.
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.