HackerRank Solution: Python Merge the Tools [Strings]

Question: Python Merge the Tools! (Strings)

Consider the following:

A string, s, of length n where s = c0c1. . . . cn-1.

An integer, k, where k is a factor of n.

We can split s into n/k substrings where each subtring, ti, consists of a contiguous block of k characters in s. Then, use each ti to create string ui such that:

The characters in ui are a subsequence of the characters in ti.

Any repeat occurrence of a character is removed from the string such that each character in ui occurs exactly once. In other words, if the character at some index j in ti occurs at a previous index < j in ti, then do not include the character in string ui.

Given s and k, print n/k lines where each line i denotes string UI.

Example:

s = “AAABCADDE”

k = 3

There are three substrings of length 3 to consider: ‘AAA’, ‘BCA’ and ‘DDE’. The first substring is all ‘A’ characters, so u1 = ‘A’. The second substring has all distinct characters, so u2 = ‘BCA’. The third substring has 2 different characters, so u3 = ‘DE’. Note that a subsequence maintains the original order of characters encountered. The order of characters in each subsequence shown is important.

Function Description

Complete the merge_the_tools function in the editor below.

merge_the_tools has the following parameters:

string s: the string to analyze
int k: the size of substrings to analyze

Prints

Print each subsequence on a new line. There will be n/k of them. No return value is expected.

Input Format:

The first line contains a single string, s.

The second line contains an integer, k, the length of each substring.

Constraints:

1 <= n <= 10^4, where n is the length of s
1 <= k <= n
It is guaranteed that n is a multiple of k.

Sample Input:

STDIN       Function
-----       --------
AABCAAADA   s = 'AABCAAADA'
3           k = 3

Sample Output:

AB
CA
AD

Explanation:

Split s into n/k = 9/3 = 3 equal parts of length k = 3. Convert each ti to ui by removing any subsequent occurrences of non-distinct characters in ti:

t0 = “AAB” – u0 = “AB”
t1 = “CAA” – u1 = “CA”
t2 = “ADA” – u2 = “AD”

Print each ui on a new line.

Possible solutions

Now, we will move toward the solutions. We already have been given the following code in the editor of the HackerRank:

def merge_the_tools(string, k):
    # your code goes here

if __name__ == '__main__':
    string, k = input(), int(input())
    merge_the_tools(string, k)

So, we have to write our solution under the merge_the_tools method:

Solution-1: Using the Dict method

Let us first solve the problem using the Python dictionary:

def merge_the_tools(string, k):
    l = len(string)//k
    for i in range(l):
        print(''.join(dict.fromkeys(string[i*k:(i*k)+k])))

if __name__ == '__main__':
    string, k = input(), int(input())
    merge_the_tools(string, k)

The merge_the_tools method takes a string and an integer as input and prints substrings of the input string with no repeated characters.

The function first calculates the number of substrings to be extracted from the input string, using integer division to determine the number of equal-sized substrings that can be created from the string. It then iterates over these substrings and uses a dictionary comprehension to create a new dictionary with the characters in the substring as keys and the values all set to None. Finally, it calls the join method on this dictionary to create a new string with no repeated characters and prints it.

Solution-2: Using Collection module

Now, we will modify the above code a little bit and will use the OrderedDict from the collection module:

from collections import OrderedDict as od

def merge_the_tools(string, k):
    l = len(string)//k
    for i in range(l):
        print(''.join(od.fromkeys(string[i*k:(i*k)+k])))


if __name__ == '__main__':
    string, k = input(), int(input())
    merge_the_tools(string, k)

This code is similar to the first one except that this time we are using OrderedDict.

Solution-3: Without using any module

Now we will not use any external methods or modules to find the solution. We will create our own method.

def merge_the_tools(string, k):
    n = len(string)

    def help_fun(items):
        seen = set()
        for i in items:
            if i not in seen:
                yield i
                seen.add(i)

    while string:
        word = string[0:k]
        string = string[k:]
        
        print (''.join(help_fun(word)))


if __name__ == '__main__':
    string, k = input(), int(input())
    merge_the_tools(string, k)

The merge_the_tool function first calculates the length of the input string and assigns it to the variable n. It then defines a nested function help_fun that takes a list of items and returns an iterator over the items, yielding only the items that have not been seen before.

The merge_the_tools function then enters a loop that continues until the input string is empty. Within the loop, it extracts a substring of length k from the start of the string and assigns it to the variable word. It then updates the value of string to remove the substring that was just extracted.

Finally, the function calls the join method on the output of help_fun applied to word, and prints the resulting string.

Summary

In this short article, we learned how we can solve the Merge the tool problem on HakerRank. We solved the problem using three different kinds of solutions.