DEV Community

Cover image for Merge the Tools! | HackerRank | Python
Retiago Drago
Retiago Drago

Posted on • Updated on

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 nk\frac n k substrings where each subtring, tit_i , consists of a contiguous block of k characters in s. Then, use each tit_i to create string uiu_i such that:

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

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

Print each subsequence on a new line. There will be nk\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

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

Sample:

AABCAAADA
3
Enter fullscreen mode Exit fullscreen mode

The Output

Sample:

AB
CA
AD
Enter fullscreen mode Exit fullscreen mode

Explanation

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

  1. t0=AABu0=ABt_0 = \text{\textquotedblleft} AAB \text{\textquotedblright} \rightarrow u_0 = \text{\textquotedblleft} AB \text{\textquotedblright}
  2. t1=CAAu1=CAt_1 = \text{\textquotedblleft} CAA \text{\textquotedblright} \rightarrow u_1 = \text{\textquotedblleft} CA \text{\textquotedblright}
  3. t2=ADAu2=ADt_2 = \text{\textquotedblleft} ADA \text{\textquotedblright} \rightarrow u_2 = \text{\textquotedblleft} AD \text{\textquotedblright}

Print each uiu_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])))
Enter fullscreen mode Exit fullscreen mode

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])))
Enter fullscreen mode Exit fullscreen mode

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 👋

Top comments (0)