3. Longest Substring Without Repeating Characters

O(n^2)

from collections import defaultdict


def solve(s):
    if not isinstance(s, str) or len(s) == 0:
        return 0
    idx_set = defaultdict(set)
    s_len = len(s)
    res = ''
    for i in range(s_len):
        for i_index in range(s_len-i):
            if s[i_index + i] not in idx_set[i]:
                idx_set[i].add(s[i_index + i])
            else:
                if len(res) < len(idx_set[i]):
                    res = ''.join(idx_set[i])
                break
    return res


print solve('pwwkew')

solution 2: maintain a window:

def solve1(s):
    if not isinstance(s, str) or len(s) == 0:
        return ''
    the_list = list()
    res = ''
    for c in s:
        if c not in the_list:
            the_list.append(c)
        else:
            if len(res) < len(the_list):
                res = ''.join(the_list)
            the_list_copy = copy.deepcopy(the_list)
            for ts in the_list_copy:
                if ts == c:
                    the_list.remove(ts)
                    break
                else:
                    the_list.remove(ts)
            the_list.append(c)
    if len(res) < len(the_list):
        res = ''.join(the_list)
    return res


print solve1("pwwkew")