// LCS Solution 1
function longestCommonSubsequence(xString, yString) {

    function recur(xArray, yArray, lcs) {
        var xElement = xArray[0];
        var yElement = yArray[0];
        // Base case --> out of string!
        // return the LCS of this section
        if (!xElement || !yElement) {
            return lcs;
        }
        // First Property
        if (xElement === yElement) {
            // append element to Subseq
            // remove element from each array
            // find LCS of remaining section
            return recur(xArray.slice(1), yArray.slice(1), lcs += xElement);
        }

        // Second Property
        if (xElement !== yElement) {
            // return the larger of the following cases:
            // Case 1, the LCS does not end in xElement
            var case1 = recur(xArray.slice(1), yArray, lcs);
            // Case 2, the LCS does not end in yElement
            var case2 = recur(xArray, yArray.slice(1), lcs);
            return case1.length > case2.length ? case1 : case2;
        }
    }

    return recur(xString, yString, '');
}

// LCS Solution #2
function longestCommonSubsequence2(xString, yString) {
    // Base case --> empty string
    if (xString === '' || yString === '') {
        return '';
    }

    // grab the first element
    var xElement = xString.charAt(0);
    var yElement = yString.charAt(0);

    // First Property: elements match
    if (xElement === yElement) {
        // return element + the LCS of remaining sections
        return xElement + longestCommonSubsequence2(xString.slice(1), yString.slice(1));
    }

    // Second Property: elements do not match
    // return the longer of the following cases:
    // Case 1, the LCS does not begin in xElement
    var case1 = longestCommonSubsequence2(xString.slice(1), yString);
    // Case 2, the LCS does not end in yElement
    var case2 = longestCommonSubsequence2(xString, yString.slice(1));
    return case1.length > case2.length ? case1 : case2;
}

console.log("1a", longestCommonSubsequence("a", "b")); // ""
console.log("2a", longestCommonSubsequence2("a", "b")); // ""
console.log("1c", longestCommonSubsequence("BANANA", "ATANA")); // "AANA"
console.log("2c", longestCommonSubsequence2("BANANA", "ATANA")); // "AANA"