How to find the number of strings that are in the particular range FAST?

How to find the number of strings that are in the particular range FAST?

I was given a question:
Given a list of strings, and a list of queries: START and END, both of
which are strings. I have to find the number of strings that are in the
range of [START, END)
For example: a list of strings: A, AA, AB, CD, ZS, XYZ a list of queries:
A, AA
A, CC
AB, ZZ
AC, CD
The output should be:
1
3
3
0
The way I approach this problem is that: while iterating through the list
of strings, I create an AVL tree by inserting new string one by one. (At
first, I used unbalanced BST but I got Time Limit.) When doing the
comparison, I use compareTo function in java String.
After creating the AVL tree, I run the query that counts from [start,
end). My method is that
1. let v = root.
2. if v==null -> return 0
else if v.value < start -> count(v.right)
else if v.value >= end -> count(v.left)
else 1 + count(v.right) + count(v.left)
However, I still got time limit pernalty :(
Therefore, I change method by creating hash function by hashing into
double and instead of using compareTo, I compared the hash value instead.
But, I still got time limit!
So, I store the value of subtree size into each vertex, and instead of
using count or the time, I add more conditional statements, some of which
can use the size of the subtree instead of calling count function
recursively.
Any suggestion to me to get it run in a particular time? :\