6
\$\begingroup\$

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.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Should 'bbb' be reduced to the empty string as well? \$\endgroup\$ Nov 19, 2016 at 9:20
  • \$\begingroup\$ @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. \$\endgroup\$ Nov 19, 2016 at 10:07

2 Answers 2

10
\$\begingroup\$

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

\$\endgroup\$
2
  • \$\begingroup\$ Thanks for the answer. Could you give an example or elaborate a bit more on what you mean? \$\endgroup\$ Nov 19, 2016 at 10:06
  • \$\begingroup\$ Ok. It makes more sense now. Thanks again for the answer :) \$\endgroup\$ Nov 19, 2016 at 20:41
6
\$\begingroup\$

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.
\$\endgroup\$
3
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ Nov 19, 2016 at 20:44
  • \$\begingroup\$ 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.) \$\endgroup\$ Nov 19, 2016 at 21:06
  • \$\begingroup\$ With your algorithm, you don't need a stack. With the new algorithm, you can use a stack. \$\endgroup\$
    – thepace
    Nov 20, 2016 at 7:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.