be smart, and your code shall be fast

if each node (except root) has a daddy, then everything's fine.
and it's cool, cuz you have a very fast way to check wether a node has a daddy without building the tree!
look at this node: RLRLRLRL
clearly his daddy has to be: RLRLRLR
so all you have to do is compare the (n-1) first characters!
first sort all the strings using insertion sort for example.
BEWARE! strcmp won't do the job
strcmp will tell you LR is smaller than R, but what you want is that a longer string is always bigger than a shorter one.
if two strings have the same length, then use strcmp.
example:
(0,LR) (1,RL) (2,) (3,R) (4,L) ()
sort them like this:
begin
""
"L"
"R"
"LR"
"RL"
end
then from the end of this list to the beginning, check for daddies and doubles!!!
you first find "RL" and you see its daddy is there ("R") so you keep going...
you need two pointers to this list, one for regular nodes and one for daddies... also don't forget the root doesn't have a daddy and don't forget to check for doubles.
also if you know RL has a dad in the list, no need to check wether RR has one!
good luck