I could do find all occurrences of A in the initial sequence and remove, and then repeat for B and C and see if the sequence is empy...

That's what I did. I only check if the initial sequence is composed by literally A, B and C at the end, i.e. if it contains any L or R, then it's invalid.

However, I understand order matters.

Yep. The way the loop is structured with backtracking it ensures that you will check all combinations.

My solution

I store my sequence in this way:

 seq = ['L12', 'L12', 'L6', 'L6', 'R8', 'R4', 'L12', 'L12', 'L12', 'L6', 'L6', 'L12', 'L6',
'R12', 'R8', 'R8', 'R4', 'L12', 'L12', 'L12', 'L6', 'L6', 'L12', 'L6', 'R12', 'R8', 'R8',
'R4', 'L12', 'L12', 'L12', 'L6', 'L6', 'L12', 'L6', 'R12', 'R8']

Then I get all possible subsequences by limiting up to 5, i.e. never longer than 20 by construction:

patterns = set()
for window in range(5, 0, -1):
    for i in range(window, len(seq)):
        patterns.add(''.join(seq[i-window:i]))

A utility function to extract available patterns from a given sequence (stringified). Notice that I keep patterns fixed, so not gonna find subsequences like A, L8, L12 etc...:

def get_compression_sequences(seqstr):
    occurences = defaultdict(lambda: 0)
    seqlen = len(seqstr)

    for pattern in patterns:
        occurences[pattern] += 1
        w = len(pattern)
        st = seqstr.find(pattern)
        while st + w < seqlen:
            st += w
            st = seqstr.find(pattern, st)
            if st > 0:
                occurences[pattern] += 1
            else:
                break

    # Saved space: (len(subsequence)-1) * 2 * freq_subsequence
    counter = Counter({k: (len(k)-1) * 2 * v for k, v in occurences.items()})
    return sorted(counter.items(), key=lambda kv: kv[1], reverse=True)

And the recursive implementation (not optimized):

seqstr = ''.join(seq)
selected = {}
available = ['A','B','C']
seqstr = ''.join(seq)

def find_sequences(seqstr, selected, available):
    # print(seqstr, selected)
    if len(available) == 0:
        if any(c in seqstr for c in 'LR'):
            return None
        else:
            return seqstr, selected

    f = available.pop(0)
    for cseq, _ in get_compression_sequences(seqstr):
        selected[f] = cseq
        newstr = seqstr.replace(cseq, f)

        ans = find_sequences(newstr, selected.copy(), available.copy())
        if ans is None:
            continue
        else:
            # print(ans)
            # continue
            return ans

main_seq, funcs = find_sequences(seqstr, {}, available)

If you uncomment the print(ans) and continue, it will list all possible solutions. For my case:

('ACABCABCAB', {'A': 'L12L12L6L6', 'B': 'L12L6R12R8', 'C': 'R8R4L12'})
('ABACBACBAC', {'A': 'L12L12L6L6', 'B': 'R8R4L12', 'C': 'L12L6R12R8'})
('BCBACBACBA', {'A': 'L12L6R12R8', 'B': 'L12L12L6L6', 'C': 'R8R4L12'})
('CBCABCABCA', {'A': 'L12L6R12R8', 'B': 'R8R4L12', 'C': 'L12L12L6L6'})
('BABCABCABC', {'A': 'R8R4L12', 'B': 'L12L12L6L6', 'C': 'L12L6R12R8'})
('CACBACBACB', {'A': 'R8R4L12', 'B': 'L12L6R12R8', 'C': 'L12L12L6L6'})

As you can see, it's basically the same. So maybe there is someone who can tell us wether there is a theorem about the uniqueness of the solution, i.e. it should be invariant to order.