Merge the Tools! | HackerRank | Python
Tags: hackerrank, computerscience, tutorial, python
Published: 2022-11-12 16:00:00

## The Problem

Consider the following:
- `n` is a length of a string `s`.
- `k` is a factor of `n`.

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

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

Given `s` and `k`, print {% katex inline %} \frac n k {% endkatex %} lines where each line `i` denotes string {% katex inline %} u_i {% endkatex %}.

Print each subsequence on a new line. There will be {% katex inline %} \frac n k {% endkatex %} 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

- {% katex inline %} 1 \le n \le 10^4 {% endkatex %}, where `n` is the length of `s`
- {% katex inline %} 1 \le k \le n {% endkatex %}
- It is guaranteed that `n` is a multiple of `k`.

Sample:

```
AABCAAADA
3
```

## The Output

Sample:

```
AB
CA
AD
```

### Explanation

Split `s` into {% katex inline %} \frac n k = \frac 9 3 = 3 {% endkatex %} equal parts of length `k = 3`. Convert each {% katex inline %} t_i {% endkatex %} to {% katex inline %} u_i {% endkatex %} by removing any subsequent occurrences of non-distinct characters in {% katex inline %} t_i {% endkatex %}:

1. {% katex inline %} t_0 = \text{\textquotedblleft} AAB \text{\textquotedblright} \rightarrow u_0 = \text{\textquotedblleft} AB \text{\textquotedblright} {% endkatex %}
1. {% katex inline %} t_1 = \text{\textquotedblleft} CAA \text{\textquotedblright} \rightarrow u_1 = \text{\textquotedblleft} CA \text{\textquotedblright} {% endkatex %}
1. {% katex inline %} t_2 = \text{\textquotedblleft} ADA \text{\textquotedblright} \rightarrow u_2 = \text{\textquotedblleft} AD \text{\textquotedblright} {% endkatex %}

Print each {% katex inline %} u_i {% endkatex %} 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.

```python
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.

```python
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](https://www.hackerrank.com/challenges/merge-the-tools/problem?isFullScreen=true)

[Let's be friend 👋](https://beacons.ai/ranggakd)