Merge the Tools! | HackerRank | Python

The Problem

Consider the following:

• n is a length of a string s.
• k is a factor of n.

We can split s into $\frac n k$ substrings where each subtring, $t_i$ , consists of a contiguous block of k characters in s. Then, use each $t_i$ to create string $u_i$ such that:

• The characters in $u_i$ are a subsequence of the characters in $t_i$ .
• Any repeat occurrence of a character is removed from the string such that each character in $u_i$ occurs exactly once. In other words, if the character at some index j in $t_i$ occurs at a previous index < j in $t_i$ , then do not include the character in string $u_i$ .

Given s and k, print $\frac n k$ lines where each line i denotes string $u_i$ .

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

The Input

• The first line contains a single string, s.
• The second line contains an integer, k, the length of each substring.

Constraints

• $1 \le n \le 10^4$ , where n is the length of s
• $1 \le k \le n$
• It is guaranteed that n is a multiple of k.

Sample:

AABCAAADA
3

The Output

Sample:

AB
CA
AD

Explanation

Split s into $\frac n k = \frac 9 3 = 3$ equal parts of length k = 3. Convert each $t_i$ to $u_i$ by removing any subsequent occurrences of non-distinct characters in $t_i$ :

1. $t_0 = \text{\textquotedblleft} AAB \text{\textquotedblright} \rightarrow u_0 = \text{\textquotedblleft} AB \text{\textquotedblright}$
2. $t_1 = \text{\textquotedblleft} CAA \text{\textquotedblright} \rightarrow u_1 = \text{\textquotedblleft} CA \text{\textquotedblright}$
3. $t_2 = \text{\textquotedblleft} ADA \text{\textquotedblright} \rightarrow u_2 = \text{\textquotedblleft} AD \text{\textquotedblright}$

Print each $u_i$ on a new line.

The Solution

The Code

Both source codes are implementations of the merge_the_tools function, which takes a string and a positive integer k as arguments. The function splits the string into substrings of length k, removes any repeated characters in each substring, and then prints the resulting substrings.

Source Code 1

The first source code uses the dict.fromkeys method to remove duplicates from each substring. This method creates a new dictionary where each character in the substring is a key, and all the values are set to None. Then, the join method is used to convert the dictionary keys back into a string. This approach works because dictionaries can only have unique keys, so any duplicates in the substring are automatically removed.

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])))

Source Code 2

The second source code uses the OrderedDict.fromkeys method from the collections module instead. This method works in the same way as dict.fromkeys, but it preserves the order of the keys in the dictionary. This means that the characters in the resulting substring are in the same order as they appeared in the original string.

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])))

Overall, both implementations achieve the same result of removing duplicates from each substring of length k. The second implementation using OrderedDict.fromkeys may be slightly slower due to the extra overhead of creating an ordered dictionary. However, it may be useful in cases where the order of the characters in each substring needs to be preserved.

Original Source

Let's be friend 👋