CODEWITHSUNDEEP
pythonstring
handavidbang
handavidbang

Reputation: 593

Super Reduced String python

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

Upvotes: 3

Views: 9155

Answers (5)

fabriziogianni7
fabriziogianni7

Reputation: 416

Solved With a while loop and string slicing!

def superReducedString(s):
   
    retString = s
    i=0

    while i < len(retString)-1:
        if retString[i] == retString[i+1]:
            if i == 0:
                retString= retString[2:]
            else:
                retString= retString[:i] + retString[i+2:]
            i = 0
        else:
            i += 1   
    
    return retString if retString else "Empty String"

It passes all the test cases :)

Upvotes: 0

Yifu Hou
Yifu Hou

Reputation: 11

I used a while loop to keep cutting down the string until there's no change:

def superReducedString(s):

    repeat = set()
    dups = set()
    for char in s:
        if char in repeat:
            dups.add(char + char)
        else:
            repeat.add(char)

    s_old = ''        
    while s_old != s:
        s_old = s
        for char in dups:
            if char in s:
                s = s.replace(char, '')
    
    if len(s) == 0:
        return 'Empty String'
    else:
        return s

Upvotes: 1

Ahmed
Ahmed

Reputation: 11

I solved it by creating a list and then add only unique letters and remove the last letter that found on the main string. Finally all the tests passed!

def superReducedString(self, s):
    stack = []
    for i in range(len(s)):
        if len(stack) == 0 or s[i] != stack[-1]:
            stack.append(s[i])
        else:
            stack.pop()
    return 'Empty String' if len(stack) == 0 else ''.join(stack)

Upvotes: 1

Tom
Tom

Reputation: 2661

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'

Upvotes: 3

Olivier Melan&#231;on
Olivier Melan&#231;on

Reputation: 22314

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 '))      # ''

Upvotes: 5

Related Questions