Brute Force Longest Common Subsequence

Question

I have come up with a brute force algorithm for finding the longest common subsequence between two given strings. It looks like it has time complexity of O(n^3). It passes all test cases I have but I'm still not sure if it will pass all test cases or not..... please let me know this is right brute force algorithm?

public String lcs(String s1, String s2) {
    int s2Start = 0;
    StringBuilder result = new StringBuilder("");
    StringBuilder temp = new StringBuilder("");

    for(int s1Start = 0; s1Start < s1.length(); s1Start++) {
        s2Start = 0; // reset
        if(temp.length() > result.length()) {
            result = temp;
        }
        temp = new StringBuilder(""); // reset

        for(int i = s1Start; i < s1.length(); i++) {
            char s1Char = s1.charAt(i);

            for(int j = s2Start; j < s2.length(); j++) {
                char s2Char = s2.charAt(j);
                if(s1Char == s2Char) {
                    temp.append(Character.toString(s1Char));
                    s2Start = j + 1;
                    break;
                }
            }
        }
    }

    if(temp.length() > result.length())
        result = temp;
    return result.toString();
}

if above code is not right, I want brute force algorithm to return longest common subsequence string,, how can i acheive this ???

Answer 1

No. This is not a right brute force algorithm to solve LCS problem. See this case -

AKBLC AMBNCK

Answer of LCS of these two strings should be 3. But in your algorithm it will calculate 2 (AK).