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.
'bbb'
be reduced to the empty string as well? \$\endgroup\$'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. \$\endgroup\$