Find the longest substring within a string that contains at most 2 unique characters.

```
substring("a") => "a"
substring("aaa") => "aaa"
substring("abacd") => "aba"
substring("abacddcd") => "cddcd"
substring("cefageaacceaccacca") => "accacca"
```

This function will take alphanumeric characters as input.

In cases where there could be more than one correct answer, the first string occurrence should be used. For example, substring('abc') should return 'ab' instead of 'bc'.

Although there are O(N^2) solutions to this problem, you should try to solve this problem in O(N) time. Tests may pass for O(N^2) solutions but, this is not guaranteed.

This question is much harder than some of the other substring questions. It's easy to think that you have a solution and then get hung up on the implementation.

Difficulty: introductory

Starter code:

def substring(s):
	

Solutions:
def substring(s):
    r, rm = [], []
    for i, x in enumerate(s):
        if x in r or len(set(r)) < 2:
            r += x;
        else:
            if len(r) > len(rm): rm = r[:]
            r = [y for y in r[-1::-1] if y == r[-1]] + [x]
    if len(r) > len(rm): rm = r[:]
    return ''.join(rm)

def substring(strng):
    best = ""
    best_end = ""
    for c in strng:
        best_end += c
        while len(set(best_end + c)) > 2:
            best_end = best_end[1:]
        if len(best_end) > len(best):
            best = best_end    
    return best

from itertools import groupby


def substring(strng):
    return max(
        enumerate(iter_candidates(strng, 2)),
        key=lambda ix: (len(ix[1]), -ix[0]),
    )[1]


def iter_candidates(strng, n):
    xs = []
    seen = set()
    for c, grp in groupby(strng):
        if len(seen) >= n and c not in seen:
            yield "".join(xs)
            seen.discard(xs[-n][0])
            del xs[:1-n]
        xs.append("".join(grp))
        seen.add(c)
    yield "".join(xs)

REGEX = __import__("re").compile(r"((.)\2*)(?=((.)\4*(?:\2|\4)*))").findall

def substring(strng):
    if len(set(strng)) <= 2: return strng
    return max((x+y for x,_,y,_ in REGEX(strng)), key=len)

def substring(stg):
    i, mi, s, ms, l = 0, 0, 3, 2, len(stg)
    while i + s <= l:
        if len(set(stg[i:i+s])) > 2:
            i += 1
        else:
            mi, ms = i, s
            s += 1
    return stg[mi:mi+ms]



def substring(strng):
    if not strng or len(strng) <= 2:
        return strng

    max_str = ''
    start_ind = 0
    next_ind = 0
    for ind, letter in enumerate(strng):
        if strng[start_ind] != letter:
            if start_ind == next_ind:
                next_ind = ind
            elif len(set(strng[start_ind:ind + 1])) > 2:
                start_ind, next_ind = next_ind, ind
                continue

        if ind - start_ind + 1 > len(max_str):
            max_str = strng[start_ind:ind + 1]

    return max_str

def substring(s, n=2):
    substr, letters, indexes = '', [''] * n, {'': 0}
    for i, c in enumerate(s, 1):
        if c not in letters:
            letters = letters[1:] + [c]
            indexes[c] = i-1
        if i - indexes[letters[0]] > len(substr):
            substr = s[indexes[letters[0]]: i]
    return substr

import re


def substring(s):
    if len(s) < 2:
        return s
    pat = re.compile(r'(.)\1*(.)(\1|\2)*', re.DOTALL)
    return max((pat.search(s, i).group() for i in range(len(s)-1)), key=len)


def substring(s):
    r = []
    for i, x in enumerate(s):
        temp = [x]
        for j in range(i+1, len(s)):
            if s[j] in temp or len(set(temp)) < 2:
                temp.append(s[j])
            else:
                r.append(''.join(temp))
                break
        r.append(''.join(temp))
    return s and max(r, key=len) or ''