Super Reduced String python

Question

I've been having problems with this simple hackerrank question. My code works in the compiler but hackerrank test is failing 6 test cases. One of which my output is correct for (I didn't pay premium). Is there something wrong here?

Prompt: Steve has a string of lowercase characters in range ascii[‘a’..’z’]. He wants to reduce the string to its shortest length by doing a series of operations in which he selects a pair of adjacent lowercase letters that match, and then he deletes them. For instance, the string aab could be shortened to b in one operation.

Steve’s task is to delete as many characters as possible using this method and print the resulting string. If the final string is empty, print Empty String

Ex.

aaabccddd → abccddd → abddd → abd

baab → bb → Empty String

Here is my code:

def super_reduced_string(s):
    count_dict = {}
    for i in s:
        if (i in count_dict.keys()):
            count_dict[i] += 1 
        else:
            count_dict[i] = 1 

    new_string = ''
    for char in count_dict.keys():
        if (count_dict[char] % 2 == 1):
            new_string += char

    if (new_string is ''):
        return 'Empty String'
    else:
        return new_string

Here is an example of output for which it does not work.

print(super_reduced_string('abab'))

It outputs 'Empty String' but should output 'abab'.

Answer 1

By using a counter, your program loses track of the order in which it saw characters. By example with input 'abab', you program sees two a's and two b's and deletes them even though they are not adjacent. It then outputs 'Empty String' but should output 'abab'.

O(n) stack-based solution

This problem is equivalent to finding unmatched parentheses, but where an opening character is its own closing character.

What this means is that it can be solved in a single traversal using a stack.

Since Python can return an actual empty string, we are going to output that instead of 'Empty String' which could be ambiguous if given an input such as 'EEEmpty String'.

Code

def super_reduced_string(s):
    stack = []
    for c in s:
        if stack and c == stack[-1]:
            stack.pop()
        else:
            stack.append(c)

    return ''.join(stack)

Tests

print(super_reduced_string('aaabab'))     # 'abab'
print(super_reduced_string('aabab'))      # 'bab'
print(super_reduced_string('abab'))       # 'abab'
print(super_reduced_string('aaabccddd ')) # 'abd'
print(super_reduced_string('baab '))      # ''

Answer 2

I solved it with recursion:

def superReducedString(s):
    if not s:
        return "Empty String"
    for i in range(0,len(s)):
        if i < len(s)-1:
            if s[i] == s[i+1]:
                return superReducedString(s[:i]+s[i+2:])
    return s

This code loops over the string and checks if the current and next letter/position in the string are the same. If so, these two letters/positions I get sliced from the string and the newly created reduced string gets passed to the function. This occurs until there are no pairs in the string.

TESTS:

print(super_reduced_string('aaabccddd')) # 'abd'
print(super_reduced_string('aa')) # 'Empty String'
print(super_reduced_string('baab')) # 'Empty String'