An alternative approach may involve trading space for time and pre-calculate mappings between letter indexes and the individual words. That would make the actual lookup function perform at \$O(1)\$ with \$O(n)\$ sacrifice for space. This may especially be useful if this function would be executed many times and needs a constant time response for the same word.
And, as this is tagged with interview-questions, I personally think it would be beneficial for a candidate to mention this idea of pre-calculating indexes for future constant-time lookups.
We could use a list to store the mappings between indexes and words:
def __init__(self, word):
self.indexes = 
for match in re.finditer(r"([A-Z][a-z]*)", word):
matched_word = match.group()
for index in range(match.start(), match.end()):
def find_word(self, index):
solver = Solver('CamelCaseString')
print(solver.find_word(2)) # prints "Camel"
print(solver.find_word(5)) # prints "Case"