3
\$\begingroup\$

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;    
  }

}
\$\endgroup\$
  • \$\begingroup\$ Thank you very much, I have checked that discussion and added a few test cases to the code. It's now passing those as well. The solution became a bit more complex as I can now see that O(n) does not seem possible in this case. \$\endgroup\$ – fpezzini Feb 25 at 19:31
  • \$\begingroup\$ I'm now trying in both directions s1 -> s2 and s2 -> s1. I'm also using string builders for efficiency, and deleting chars on s1 as well. The for loop ensures it does not try to find a solution when there are fewer characters than the current solution. \$\endgroup\$ – fpezzini Feb 25 at 19:33
  • \$\begingroup\$ I rolled back your last edit. After getting an answer you are not allowed to change your code anymore. This is to ensure that answers do not get invalidated and have to hit a moving target. If you have changed your code you can either post it as an answer (if it would constitute a code review) or ask a new question with your changed code (linking back to this one as reference). Refer to this post for more information \$\endgroup\$ – Sᴀᴍ Onᴇᴌᴀ Feb 26 at 21:13
  • \$\begingroup\$ Oh, ok, sorry about that. \$\endgroup\$ – fpezzini Feb 26 at 21:36
4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Thanks, nice catch! I have edited the code to account for that test case. The complexity has now increased considerably from quadratic to cubic. In my tests performance starts to suffer when there are over 300 characters in a word. I need to think a bit more if there's a way to improve performance, or hopefully get it back to quadratic time complexity. \$\endgroup\$ – fpezzini Feb 26 at 21:11
  • 1
    \$\begingroup\$ @fpezzini maybe you should think about a dynamic programming solution. After all, you tagged this question with "dynamic programming" but your solution makes no use of it. \$\endgroup\$ – JS1 Feb 27 at 9:31
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Thanks a lot for the feedback. I have renamed the method to "find" which is more descriptive of what it does. When you call longestSubsequence.find it will make sense. I like to have a class having a single responsibility. \$\endgroup\$ – fpezzini Feb 26 at 21:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.