Problem: Merge The Tools

This problem is straightforward to understand, so I don't need to have any further explanation. There are two main parts we need to solve:

• Splitting the strings into sub-strings t
• Removing duplicates in each sub-strings t to obtain the corresponding string u

The first method to extract sub-strings t is to use double for loops, or list-comprehension in python:

def merge_the_tools(string, k):
    t = [string[i:i+k] for i in range(0, len(string), k)]

Time complexity for this operation would be O(len(string)*(k)) as at each iteration, it performs string slicing of length k. There is another way to achieve the same result, that is using regex:

import re
def merge_the_tools(string, k):
    t = re.findall('.'*k, string)

The complexity of classic regular expression can be tricky, which can be converted to deterministic finite automaton problem. For your interest, the paper Regular Expression Matching Can Be Simple And Fast explained and discussed details on the topic. In general, running DFA-compiled regex takes up the time complexity of O(n) with n as length of the input string.

Finally, we need to print out each sub-string with no duplicate character. We can simply join each sub-string in the array as set() or keys of dict(). Since the order of the characters matters, we choose the latter for implementation:

for u in t:
    print("".join(dict.fromkeys(u)))

Solution for either extracting sub-strings by implementing list-comprehension or regex passed all the test cases in HackerRank.