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.