Reduce as many adjacent chars as possible in string

This code is meant to reduce a given string as much as possible by deleting adjacent characters. Here are some examples:

reduce('aa') = 'Empty String'
reduce('ab') = 'ab'
reduce('abba') = 'Empty String' # remove 'bb' then 'aa'
reduce('bbb') = 'b'  # can only delete 2 chars at a time

This is based off this HackerRank question.

I'm doing this to improve my style and to improve my knowledge of fundamental algorithms/data structures for an upcoming coding interview.

def reduce(s):
    cur_chars = list(s)
    while cur_chars:
        new_chars = do_deletions(cur_chars)
        if new_chars == cur_chars:  # if nothing deleted then return
            new_s = ''.join(cur_chars)
            return new_s
        else:
            cur_chars = new_chars  # do another round of deletions
    return 'Empty String'

def do_deletions(org_chars):
    if len(org_chars) == 1:
        return org_chars

    new_chars = []
    i = 0
    while i < len(org_chars):
        if i == len(org_chars) - 1:
            new_chars.append(org_chars[i])
            i += 1
        elif org_chars[i] == org_chars[i+1]:
            i += 2  # don't include char i and i+1
        elif org_chars[i] != org_chars[i+1]:
            new_chars.append(org_chars[i])
            i += 1
    return new_chars

I was originally going to do deletions using 2 consecutive del commands (O(n)) but then I thought this performance would be too bad for an interview. Instead I opted to not do any deletions and just use appends to create gradually reduced strings. If my original approach would have been fine for an interview then let me know.

I think this algorithm is O(n^2) time and O(n) space. Any suggestions about how I can improve the complexities are welcome.

This is related to the task of checking for matching parentheses. You can solve it in a single pass if you compare the current org_char to the latest new_char, and if they are the same, remove the latest new_char and skip the current org_char.

The do_deletions function already defines the org_chars and the new_chars. Instead of comparing only the org_chars, you should check whether len(new_chars) > 0 and org_chars[i] == new_chars[-1].

StackExchange Code Review Q#147494, answer score: 10