The Problem
Consider the following:

n
is a length of a strings
. 
k
is a factor ofn
.
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 ofs
 $1 \le k \le n$
 It is guaranteed that
n
is a multiple ofk
.
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 nondistinct characters in
$t_i$
:
 $t_0 = \text{\textquotedblleft} AAB \text{\textquotedblright} \rightarrow u_0 = \text{\textquotedblleft} AB \text{\textquotedblright}$
 $t_1 = \text{\textquotedblleft} CAA \text{\textquotedblright} \rightarrow u_1 = \text{\textquotedblleft} CA \text{\textquotedblright}$
 $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.
Top comments (0)