How to get string between two certain strings in Swift?

Given two strings over an alphabet of size N, what is the most efficient technique to find the string that lies in the middle? On should use dictionary order to order the string.

• For example, say max length is 10. and the alphabet consists of 26 characters a-z. The input strings are "beginning"(size:9) and "ending"(size: 6). We have to find a string that lies exactly at the middle. Basically we have to find the middle string among all possible 10 character strings between "beginning" and "ending". Note that, following dictionary order, "beginning" is smaller than "ending".

• Answer:

  Let's consider that you know the ordinal number of the middle word. For instance, if the lowest string is the 1st and the greatest string is the 10th, then the middle word is the 5th, right? (I will show how to calculate these numbers). So, the problem now is how to find the nth string formed with the characters of the alphabet. Let's solve this problem with strings of size exactly 3 (it's easy to generalize for string of size <= 3) and alphabet = {a,b,c}. Imagine that I want to find the 23th string (out of 3^3 = 27 strings). Which would be the 1st character? If we pick the "a", then we're left with 2 more letters to choose, what give us 3^2 = 9 possible strings. It's not enough, because we want the 23th. So let's try the "b". We have the 9 strings with the "a"as first character and more 9 strings with the "b"(same reasoning). This give us 18 strings. So, we conclude that the first character must be the "c". When we put "c" as first character we skip 18 strings, so now we want the 23-18=5th string of size 2. As you might have realized, this is a recursive procedure. We apply the same reasoning to find out the second character ("b"in this example) and the third ("b"). This give us the string "cbb". Now, in order to find out the ordinal numbers of the two input strings, we just apply this procedure backwards. For instance: what's the ordinal number of "bca"? with the "b" we skip 9 strings that start with "a". with the "c" we skip 6 strings (that have "a" or "b"as second character) with the final "a" we skip 1 string Therefore: 9 + 6 + 1 = 16. "bca" is the 16th string. So, let's calculate the overall complexity: * O(n) to find the ordinal number of the lowest string * O(n) to find the ordinal number of the greatest string * O(n) to find the nth string from its ordinal number So your problem can be solved in linear time. PS: sorry for any english mistakes that I (surely) made. PS2: feel free to ask for further clarifications.