1
$\begingroup$

I've been given the question in the title:

Create a data structure that can insert a string S in O(|S|), string may belong to group A or B (or both). The structure should be able to return a string in it that the amount of lexicographic smaller string from A in the structure equals the amount of lexicographic larger string from B, in time complexity O(|Smax|) (the size of longest string in the structure).

I should solve it using simple trie trees. My idea was saving in every intersection in the tree the amount of leaves in the sub tree from group A and group B (two different variables).

But that doesn't seem to be enough because I wasn't able to build a search algorithm with this data that works within the time complexity, there are certain cases I cannot definitively choose whether to proceed from current intersection with letter x or letter x+1 because the difference between the smaller leaves in A and larger leaves in B is 1 and the string could exist in the sub tree of letter x or x+1 (depends on the inner order in these sub trees).

Would really appreciate any help with this.

$\endgroup$
6
  • $\begingroup$ Did you notice that such a string does not necessarily exist? For example, suppose that the structure is made of $4$ elements: $aa$ and $ab$ (both in $A$), $ba$ and $bb$ (both in $B$). No string among the 4 separates the structure as wanted. (I supposed here that the inequalities cannot be an equality, but there are also counter-examples in the other case). Perhaps you tolerate a difference of at most $1$? $\endgroup$
    – Nathaniel
    May 21 at 20:13
  • $\begingroup$ @Nathaniel yes I've noticed this, I failed to mention it but in such case I need to return an error. I didn't quite understand the bit of tolerating at most 1 though, could you elaborate? $\endgroup$ May 21 at 21:15
  • $\begingroup$ It is always possible to find a string $s$ such that the difference between the number of string of $A$ smaller than $s$ and the number of string of $B$ greater than $s$ is at most $1$. I wondered if you would consider such a string as a good answer. $\endgroup$
    – Nathaniel
    May 22 at 9:13
  • $\begingroup$ Where did you encounter this task? I encourage you to credit the original source. Note that we require proper attribution for all copied material: cs.stackexchange.com/help/referencing $\endgroup$
    – D.W.
    May 23 at 6:55
  • $\begingroup$ @D.W. it was part of an assignment given at my university $\endgroup$ May 30 at 11:15

1 Answer 1

1
$\begingroup$

Your idea to use a trie is good. I think that what might do the trick is only to store additionnal information at each node: the number of strings of $A$ and of $B$ contained in the corresponding subtree.

This does not change the time complexity of usual operations on tries, you only need to adjust the numbers in the ancestors of the string you added/deleted.

Moreover, it allows you to search for "the middle string" when doing the required request: given a node $N(x, [t_1, t_2, …, t_k])$, if we denote $a_1,…, a_k$ the number of strings of $A$ in $t_1, …, t_k$ and $b_1, …, b_k$ the number of strings of $B$ in those trees, then you want to continue the search in subtree $t_i$ such that $\sum\limits_{j = 1}^{i-1}a_j < \sum\limits_{j = i}^{k}b_j$ and $\sum\limits_{j = 1}^{i}a_j \geqslant \sum\limits_{j = i+1}^{k}b_j$.

Since the alphabet is of constant size, the overall operation is at most in the height of the trie, or similarly the maximum size of a string in the trie.

Note: I supposed here that children are ordered by their roots.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.