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

• Should 'bbb' be reduced to the empty string as well? Nov 19 '16 at 9:20
• @MathiasEttinger It should return just 'b' since you can only delete 2 characters at a time. I should have made that clearer in the question. I'll edit it to make it clear. Nov 19 '16 at 10:07

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

• Thanks for the answer. Could you give an example or elaborate a bit more on what you mean? Nov 19 '16 at 10:06
• Ok. It makes more sense now. Thanks again for the answer :) Nov 19 '16 at 20:41

• 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.
• Thanks for the answer and for elaborating a bit more on Roland's answer. I like how you provided the complexities for the new approach. Nov 19 '16 at 20:44
• You don't really need a separate stack, do you? You can use the output buffer (or the end-of-result position if you modify a buffer in-place) as a stack. It's slightly more complicated if a run of 3 or more chars should still be eliminated, rather than just removing matching pairs. Since then you can't forget about what you've already seen after seeing a pair. (Oh, but I see that's not the case, bbb => b.) Nov 19 '16 at 21:06
• With your algorithm, you don't need a stack. With the new algorithm, you can use a stack. Nov 20 '16 at 7:11