# Find a string between two groups A,B that have an amount of smaller strings in A as it has larger strings in B

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.

• 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$? May 21 at 20:13
• @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? May 21 at 21:15
• 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. May 22 at 9:13
• 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
– D.W.
May 23 at 6:55
• @D.W. it was part of an assignment given at my university May 30 at 11:15

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.
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$$.