Hackerrank - Super Reduced String Solution
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 each operation he selects a pair of adjacent lowercase letters that match, and 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
Complete the superReducedString function in the editor below. It should return the super reduced string or
Empty String if the final string is empty.
superReducedString has the following parameter(s):
- s: a string to reduce
A single string, .
If the final string is empty, print
Empty String; otherwise, print the final non-reducible string.
Sample Input 0
Sample Output 0
Steve performs the following sequence of operations to get the final string:
aaabccddd → abccddd → abddd → abd
Sample Input 1
Sample Output 1
aa → Empty String
Sample Input 2
Sample Output 2
baab → bb → Empty String
Solution in Python
import re def superReducedString(s): while re.search(r"(\w)\1", s): s = re.sub(r"(\w)\1", "", s) return s or "Empty String" print(superReducedString(input()))
The question says "In each operation, he selects a pair of adjacent lowercase letters that match, and he deletes them."
Which means we have to remove any 2 repeating characters.
I have used a while loop because we have to replace all 2 repeating characters, and not only one.
Example let our string s = "aabbabb"
In our first loop re.search will match "aa".
We use re.search only to check if there is any repeating characters. Then we will use re.sub to remove any 2 repeating character
s = "aabbabb" Loop 1. Matches -> "aa" ,"bb", "bb" New String -> "a" No more two repeating characters. Output -> "a"
Example let our string s = "abbabb"
In our first loop re.search will match "bb".
Then we will use re.sub to remove any 2 repeating character
s = "abbabb" Loop 1. Matches -> "bb" , "bb" New String -> "aa" Loop 2. Match -> "aa" New String -> "" No more two repeating characters. Output -> "Empty String"