Algorithm to Generate Alphabetic String That is Alphabetically Between Two Other Strings?

Question

A problem I'm trying to solve: given that you have two distinct strings composed of the lower case letters a through z, find a string between the two strings such that further in-between strings can always be found.

Further detail:

Given that 'a' comes before 'b' alphabetically, there are an infinite number of strings between 'a' and 'b', when sorted as a dictionary would: 'aa', 'aaa', 'aaaa', 'ab', 'aba', etc. However, there are not an infinite number of strings between all strings - nothing comes between 'a' and 'aa'. Further, between 'a' and 'aaa' there exists only one in-between string 'aa'.

What is an algorithm that can find a string X that comes alphabetically between 'a' and 'b' that also satisfies the condition that there are infinite number of strings between 'a' and X as well as X and 'b'?

Answer 1

assuming that one can insert an infinite number of strings between the two strings.

If the lower string is shorter, add as many 'a's as to make the lengths equal then add a 'b' to the middle string. If the upper word is shorter make the middle string equal the lower string and append z to the middle string. If the two strings have equal length, use either method.

Answer 2

You have stated everything you need to know to find a solution. Basically, a finite number of strings exist only if one string is a prefix of the other and the rest is a string of "a"s.

Otherwise, you can find an infinite number of in-between strings.