9
$\begingroup$

My question is generalizable to arrays of any type but I'll use strings to keep it short.

We take a couple of strings as an input. Let's denote them ${S_1,...S_n}$. (Ex: "ABEF" and "CDE"). The output $U$ must fulfill the following conditions:

  • The output must contain the entire "vocabulary" of all of the inputs and not more: $x\in U \Leftrightarrow \exists i : x\in S_i$
  • Each element in the output appears only once in the output.
  • The elements in the output keep their relative ordering from their original strings. So if 'A' comes before 'B' in the string $S_i$, then 'A' must come before 'B' in the output $U$.

The problem can have multiple solutions or no solutions. I'm fine with finding just one of them. Some examples might be:

inputs possible solutions
ABEF, CDE ABCDEF, CDABEF, CABDEF...
ABEF, CDE, BC ABCDEF (only solution)
ABEF, CDE, CB CDABEF, CADBEF, ...

I found this question with a similar algorithm. However, their algorithm allows repeated elements in their output.

Is there a name for this algorithm? What's the time complexity? Does anyone know an implementation in a Python library? Thanks!

Clarifications:

  • the inputs do not have an ordering. The ordering is given by the inputs themselves. That's why "CDABEF" is a valid solution in the first example.
  • If the problem does not have a solution, throw an exception.
Improve this question
$\endgroup$
3
  • $\begingroup$ Are the input arrays sorted? (They are in your examples are.) If so, merge step of merge-sort. $\endgroup$ Commented Jun 23, 2022 at 14:38
  • $\begingroup$ What happens if the problem has no solution, for instance input={AB, BA}? $\endgroup$ Commented Jun 23, 2022 at 15:18
  • $\begingroup$ I will assume your second condition means "reduce duplicate elements to a single occurrence", as the attitude "I did not repeat anything, those elements were already present multiple times" does not seem to match your intent. But then your two conditions are not logically consistent: an element in the output does not correspond to a well defined element of the input, so how can it preserve "its" relative ordering to another such ill defined element? You need to be clearer about what you mean; a couple of examples helps, but does not substitute for a proper formulation. $\endgroup$ Commented Jun 24, 2022 at 8:19

1 Answer 1

Reset to default
23
$\begingroup$

You can easily solve your problem by creating a directed graph $G=(V,E)$ in which $V$ is the set of all characters that appear in some input string and $E$ contains the edge $(u,v)$ if character $u$ is immediately followed by character $v$ in some string.

This graph has $O(n)$ edges where $n$ is the total length of the input (i.e., the sum of the strings' lengths) and can be built in $O( \min\{n+|\Sigma|, n \log n\} )$ worst-case time, where $\Sigma$ is your alphabet (if the alphabet has constant size then this is just $O(n)$) or $O(n)$ expected time.

Then your problem admits a solution if and only if $G$ is a directed acyclic graph (DAG). This can be tested in $O(n)$ time. If $G$ is indeed a DAG, any topological ordering of the vertices in $G$ is a valid solution to your problem. A topological ordering of $G$ can be found in $O(n)$ time.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Are you sure the graph can be built with the complexity you say? When traversing the first string, you can make a new node for everything you encounter (presumably), but when traversing the second string, you must at least determine for each letter whether we have already seen that letter in the first string. That seems like it needs $O(n\mathrm{log}\,n)$ time to me unless you pull some suspicious tricks like claiming that hashing is constant-time or something. $\endgroup$ Commented Jun 24, 2022 at 0:16
  • $\begingroup$ @DanielWagner If the alphabet is reasonably sized, you can use an array with one entry per member of the alphabet and then it is constant-time, with no hashing :) $\endgroup$ Commented Jun 24, 2022 at 1:25
  • $\begingroup$ @hobbs Isn't that still $O(n\mathrm{log}\,|\Sigma|)$? $\endgroup$ Commented Jun 24, 2022 at 2:46
  • 1
    $\begingroup$ $O(\min \{n + |\Sigma|, n \log n\})$ is never asymptotically worse than $n \log |\Sigma|$. If $|\Sigma| = O(n)$, then $O(\min \{n + |\Sigma|, n \log n\}) = O(n)$. If $|\Sigma| = \Omega(n^c)$ for some constant $c>0$ (consider in particular $c=1$) then $O(\min \{n + |\Sigma|, n \log n\}) = O(n \log n) = O(n \log |\Sigma|)$. $\endgroup$ Commented Jun 24, 2022 at 11:21
  • $\begingroup$ @DanielWagner you can generate a list of all edges, sort it, and remove duplicates. The list constains $O(n)$ edges. You can sort the list in tine $O(n \log n)$ using any asymptotically optimal comparison-based algorithm or you can associate each character in $\Sigma$ to a distinct integer in $N = \{1, \dots,|\Sigma|\}$ so that each edge is a pair in $N^2$. These pairs (u,v) can be sorted (lexicographically) by first sorting w.r.t. $v$ (in $O(n+|\Sigma|)$ time by creating one bucket for each character in $\Sigma$) and then sorting again w.r.t. $u$ (the sorting algorithm needs to be stable). $\endgroup$ Commented Jun 24, 2022 at 11:27

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.