Reduce as many adjacent chars as possible in string

Question

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.

Answer 1

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].

Answer 2

About the Algorithms:

How can your be improved:

• Lets take an example: reduce ('abba');

Current algorithm:

do_delete('a') would return 'a'
do_delete('ab') would return 'ab'
do_delete('abb') would return 'a'
do_delete('abba') would return ''

Change the argument to accept the new_chars + the new letter and compare just 'i' with 'i-1';

  do_delete('a') would return 'a'
  do_delete('ab') would compare 'b' with 'a'  and return 'ab'
  do_delete('abb') would compare 'b' with 'b' and return 'a'
  do_delete('aa') would compare 'a' with 'a' and return 

Benefits: O(1) comparison.

Elaborating Roland's answer: You can use a STACK {Complexity: Time O(n), Space O(n)}.

• Suppose the input is "abbccaa".
• Take a letter, check the top of the stack. If it matches, pop the top and ignore the letter.
• If the letter doesn't match the top of the stack, push the letter and continue.
• After the array traversal completes, check the stack. If its empty, return "Empty string" else return the reversed string formed by concatenation of values in the stack.