gistfile1.py

def merge_candidates(left, right, identical_left_flag, identical_right_flag):

    candidates = []
    if identical_left_flag or identical_right_flag:
        if identical_left_flag and not identical_right_flag:
            candidates.append(left[0])
        if not identical_left_flag and identical_right_flag:
            candidates.append(right[0])
        elif left[0] == right[0]:
            return left, True
        else:
            candidates.append(left[0])
            candidates.append(right[0])

        return candidates, False

    for x in left:
        for y  in right:
            if x == y:
                candidates.append(x)


    return candidates, False


def find_candidate_cards(cards):
    nCards = len(cards)
    if nCards == 1:
        candidate = cards
        return candidate, True
    else:
        candidate_left, identical_left_flag = find_candidate_cards(cards[:nCards/2])
        candidate_right, identical_right_flag = find_candidate_cards(cards[nCards/2:])
        
        candidates, identical_flag = merge_candidates(candidate_left, candidate_right, identical_left_flag, identical_right_flag)
        
        return candidates, identical_flag




test = 'AABADDDD'
candidates, identical_flag = find_candidate_cards(test)
print candidates