def LCS(String1, String2):
    if String1 == '' or String2 == '':
        return 0
    if String1[0] == String2[0]:
        return 1 + LCS(String1[1:], String2[1:])
    option1 = LCS(String1, String2[1:])
    option2 = LCS(String1[1:], String2)
    return max(option1, option2)

# LCS('AGGACAT', 'ATTACGAT')
# 5

def fastLCS(StringA, StringB):
    return fastLCSR(StringA, StringB, {})

def fastLCSR(StringA, StringB, MemoDict):
    if (StringA, StringB) in MemoDict:
        return MemoDict[(StringA, StringB)]
    if StringA == '' or StringB == '':
        return 0
    if StringA[0] == StringB[0]:
        result = 1 + fastLCSR(StringA[1:], StringB[1:], MemoDict)
    else:
        option1 = fastLCSR(StringA, StringB[1:], MemoDict)
        option2 = fastLCSR(StringA[1:], StringB, MemoDict)
        result = max(option1, option2)
    MemoDict[(StringA, StringB)] = result
    return result

# fastLCS('AGGACAT', 'ATTACGAT')
# 5

import random

def random_DNA(N):
    l = []
    for _ in range(N):
        b = random.choice(['A', 'T', 'C', 'G'])
        l.append(b)
    return ''.join(l)

# random_DNA(10)
# 'ACTGCTAATG'
# random_DNA(50)
# 'CCTGACCGTGGCAAACTGTGCCACGGGAGGCGGAACGCTGCTTGTCCACG'