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.