Write a function called `LCS` that accepts two sequences and returns the longest subsequence common to the passed in sequences.

### Subsequence
A subsequence is different from a substring. The terms of a subsequence need not be consecutive terms of the original sequence.

### Example subsequence
Subsequences of `"abc"` = `"a"`, `"b"`, `"c"`, `"ab"`, `"ac"`, `"bc"` and `"abc"`.

### LCS examples
```python
lcs( "abcdef" , "abc" ) => returns "abc"
lcs( "abcdef" , "acf" ) => returns "acf"
lcs( "132535365" , "123456789" ) => returns "12356"
```

### Notes
* Both arguments will be strings
* Return value must be a string
* Return an empty string if there exists no common subsequence
* Both arguments will have one or more characters (in JavaScript)
* All tests will only have a single longest common subsequence. Don't worry about cases such as `LCS( "1234", "3412" )`, which would have two possible longest common subsequences: `"12"` and `"34"`.

Note that the Haskell variant will use randomized testing, but any longest common subsequence will be valid.

Note that the OCaml variant is using generic lists instead of strings, and will also have randomized tests (any longest common subsequence will be valid).

### Tips

Wikipedia has an explanation of the two properties that can be used to solve the problem:

- [First property](http://en.wikipedia.org/wiki/Longest_common_subsequence_problem#First_property)
- [Second property](http://en.wikipedia.org/wiki/Longest_common_subsequence_problem#Second_property)

Difficulty: introductory

Starter code:

def lcs(x, y):
	

Solutions:
def lcs(x, y):
    if len(x) == 0 or len(y) == 0:
        return ''
    if x[-1] == y[-1]:
        return lcs(x[:-1], y[:-1]) + x[-1]
    else:
        lcs1 = lcs(x,y[:-1])
        lcs2 = lcs(x[:-1],y)
        if len(lcs1) > len(lcs2):
            return lcs1
        else:
            return lcs2


from itertools import combinations

def subsequences(s):
    """Returns set of all subsequences in s."""
    return set(''.join(c) for i in range(len(s) + 1) for c in combinations(s, i))

def lcs(x, y):
    """Returns longest matching subsequence of two strings."""
    return max(subsequences(x).intersection(subsequences(y)), key=len)

def lcs(x, y):
  res=[]
  i=0
  for item in y:
     if item in x[i:]:
        res+=[item]
        i=x.index(item)+1
  return "".join(res)

def lcs(x, y):
    if not x or not y: return ""
    if x[0] == y[0]: return x[0] + lcs(x[1:], y[1:])
    
    return max(lcs(x[1:], y), lcs(x, y[1:]), key=len)


def lcs(string1, string2):
    if not string1 or not string2:
        return ''
    if string1[0] == string2[0]:
        return string1[0] + lcs(string1[1:], string2[1:])

    return max(lcs(string1, string2[1:]), lcs(string1[1:], string2), key=len)


def lcs(x, y):
    try:
        if x[0] == y[0]:
            return x[0] + lcs(x[1:], y[1:])
        else:
            return max(lcs(x[1:], y), lcs(x, y[1:]), key = len)
    except IndexError:
        return ''

def lcs(x, y):
    if not (x and y):
        return ''
    if x[-1] == y[-1]:
        return lcs(x[:-1], y[:-1]) + x[-1]
    else:
        return max(lcs(x[:-1], y), lcs(x, y[:-1]), key=len)

lcs = (lambda y: y(y))(lambda lcs: lambda x, y: '' if not x or not y else lcs(lcs)(x[:-1], y[:-1]) + x[-1] if x[-1] == y[-1] else max(lcs(lcs)(x[:-1], y), lcs(lcs)(x, y[:-1]), key = len))