--- title: Double or One Thing date: 2023-04-19 17:08:42 -0600 categories: [Technical Logs, Individual] tags: [python] math: true --- Try this problem by yourself first! Check the [Code Jam Page](https://codingcompetitions.withgoogle.com/codejam/round/0000000000877ba5/0000000000aa8e9c). ## Overview We have a string of uppercase English characters. We can double or not every character of the string. If we had the set of all possible results and sort them alphabetically, which string would come first? Our only control over the string is doubling or not each character. Sorting alphabetically means comparing letters and choosing the one that appears before in the alphabet. If we had the string *AB*, we would highlight the *A* because *AAB* comes before *AB*. Why does *AAB* comes before *AB*? Because we compare the second *A* of *AAB* with the *B* of *AB*. *A* comes before *B* in the alphabet, therefore *AAB* comes before *AB*. Let's see another simple example. If our string is *BA*, then we won't highlight the first *B*, because *BBA* would come after *BA*. From another point of view, we're comparing each letter with the immediate next letter. In the case of *BA*, we're comparing the *B* with the *A*. Because the *B* comes after the *A*, we won't highlight the *B*. What if we're seeing the last letter? In the case *ABC*, do we highlight the *C*? No, we won't highlight it, because *ABC* comes before *ABCC*. In this sense, we'll never highlight the last letter. Finally, what if we're comparing the same letter? Let's say we want to know if we have to highlight the first *O* in *LOOK*. Instead of comparing the first *O* with the second *O* (that doesn't give us any information), we will compare it with the first distinct letter. In this case, that letter is *K*. Now we can have the same conclusions as before, but applied to all repeating letters. I.e., *O* comes after *K*? Then don't highlight any *O*. What about *FEEL*? Instead of comparing the first *E* with the second *E*, compare it with *L*. *E* comes before *L*? Then highlight ALL *E*'s. That's a very condensed overview of the solution and why it works.

O O O

o o o

...

O O O

o o o

...

## Solution The big picture of the solution is as following: 1. Walk through the character string letter by letter. 1. If the current letter comes before the next letter in the alphabet, **highlight it**. 1. If the current letter comes after the next letter in the alphabet, **don't highlight it**. 1. If the current letter is the same as the next letter, keep walking until you find a letter different from the current one. Highlighting all the letters or none of them will depend on if the current letter comes before or after the first different one, respectively. 1. The last letter **will never be highlighted**. We illustrate two examples following the procedure. #### RIDE 1. **R**IDE $\rightarrow$ The *R* comes after the *I*. Hence, we won't highlight the *R*. 1. R**I**DE $\rightarrow$ The *I* comes after the *D*. Therefore, we won't highlight the *I*. 1. RI**D**E $\rightarrow$ The *D* comes before the *E*. Now we will highlight the *D*. 1. RID**E** $\rightarrow$ We won't highlight the *E* because it is the last letter. The resulting string is RIDE. Just as we saw in the [context section](#context), this is the desired output. #### FEEELING 1. **F**EEELING $\rightarrow$ *F* > *E*. Therefore, *F* is not highlighted. 1. F**E**EELING $\rightarrow$ *E* = *E*. We'll keep walking. 1. F**E**EELING $\rightarrow$ *E* = *E*. Keep on walkiiiing. 1. F**E**EELING $\rightarrow$ *E* < *L*. Hence, we'll highlight all *E*'s. 1. FEEE**L**ING $\rightarrow$ *L* > *I*. We won't highlight the *L*. 1. FEEEL**I**NG $\rightarrow$ *I* < *N*. The *I* must be highlighted. 1. FEEELI**N**G $\rightarrow$ *N* > *G*. You better not touch the *N*. Don't highlight it! 1. FEEELIN**G** $\rightarrow$ *G* > *_*. Last letter must never be highlighted. >:( Therefore, the solution is FEEELING. Is this the right solution? Lets use the brute force way! This means: listing all highlighting possibilities and sorting them. We obtain: | 1. FEEELING $\rightarrow$ FEEEEEELIING | 5. FEEELING $\rightarrow$ FEEEEEELING | ... | 253. FEEELING $\rightarrow$ FFEEELLING | | 2. FEEELING $\rightarrow$ FEEEEEELIINGG | 6. FEEELING $\rightarrow$ FEEEEEELINGG | ... | 254. FEEELING $\rightarrow$ FFEEELLINGG | | 3. FEEELING $\rightarrow$ FEEEEEELIINNG | 7. FEEELING $\rightarrow$ FEEEEEELINNG | ... | 255. FEEELING $\rightarrow$ FFEEELLINNG | | 4. FEEELING $\rightarrow$ FEEEEEELIINNGG | 8. FEEELING $\rightarrow$ FEEEEEELINNGG | ... | 256. FEEELING $\rightarrow$ FFEEELLINNGG |

Source: Trust me, bro.

That's the right solution! But wait... Why is it the right solution? Why does the procedure works? ### Why does it works? In this work we will divide the explanation in two parts: with and without repeating consecutive letters. We will start with no repeating letters, as it is the easiest one. #### Without repeating letters In the procedure we walk through each character of the string. For each one we decide if we highlight it or not. Why does the procedure work this way? Let's review the example of RIDE more closely. We will start with the letter **R** and see what happens if we highlight it and what happens if we don't.

RIDE

RIDE

RIDE

RIDE

| Highlighting? | After doubling | Comparing | Which one won? | |:-|:-|:-|:-| | Highlighted | RIDE $\rightarrow$ RIDEE | RIDE **E** | Comes second. | | Not highlighted | RIDE $\rightarrow$ RIDE | RIDE | Comes **FIRST**! | Because *RIDE* is a subset of *RIDEE*, *RIDEE* comes after *RIDE*. We better **NOT** highlight the *E*. This is exactly why we compare the current letter vs the next one. If the current letter of the string appears before in the alphabet with respect to the next letter of the string, we better have more of the current letter. If the current letter appears after than the next letter, we better jump to the next one as soon as we can. On the other hand, highlighting the last character will only make it a superset of the non-highlighted one. In the alphabetical order, we prefer our word not to be the superset one. All of this can be represented with the following code: ```python def first_alphabetically(my_str: str) -> str: result = [] current = 0 while current < len(my_str) - 1: # If the current letter comes before the next letter, highlight it. if my_str[current] < my_str[current + 1]: result += my_str[current] * 2 current += 1 # If the current letter comes after the next letter, don’t highlight it. elif my_str[current] > my_str[current + 1]: result += my_str[current] current += 1 # If they're the same letter... We will see it later. else: pass # The last letter will never be highlighted. result += my_str[-1] return ''.join(result) ``` {: file="solution.py"} #### With repeating letters What happens when you have to compare between the same letter? Let's look at some examples:

LOOK

FEEL

SEE

LOOOOOOK

FEEEEEEL

SEEEEEE

| Highlighting? | After doubling | Comparing | Which one won? | |:-|:-|:-|:-| | Highlighted | SEEEEEE $\rightarrow$ SEEEEEEE | SEEEEEE **E** | Comes second. | | Not highlighted | SEEEEEE $\rightarrow$ SEEEEEE | SEEEEEE | Comes **FIRST**! | The least letters we have at the end, the better. Is it now clear why if we have repeating letters, we compare the first repeating letter with the first distinct letter? We can code this in the following way: ```python def give_me_last_equal(string: str, position: int) -> int: """ Given a position in a string, output the last position such as: string[position] == string[position + 1] == ... == string[last_position]. """ test_letter = string[position] last_position = position while last_position < len(string) - 1 and test_letter == string[last_position + 1]: last_position += 1 return last_position def first_alphabetically(my_str: str) -> str: while current < len(my_str) - 1: # Already seen code. else: # Search for the index of the first letter distinct from the # current letter. last_equal = give_me_last_equal(my_str, current) # If the string ends with repeating letters, don't highlight them. if last_equal == len(my_str) - 1: result += my_str[current] * (last_equal - current) break # If the current letters comes before, highlight all of them. elif my_str[last_equal] < my_str[last_equal + 1]: result += my_str[current] * (2 * (last_equal - current + 1)) # If the current letters comes after, don't highlight them. else: result += my_str[current] * (last_equal - current + 1) # Walk `last_equal - current + 1` letters forward. current += last_equal - current + 1 # Already seen code. ``` {: file="solution.py"} And now you know why the proposed solution works that way. Congratulations! :D

O O O

o o o

...

## Alternative Solutions Only one alternative solution came to my mind: **brute force**. As explained at the beginning of the [solution section](#solution), it consists on: 1. Generating all possible highlightings. 1. Sorting the results. 1. Retrieving the first one that appeared. Although the biggest pro in this solution is its simplicity, the biggest con is what makes this solution inviable. Each letter can be highlighted or not, independently of the other letters. Considering a string of $n$ characters, we have a total number of $2^n$ possible highlightings. On a set of small strings, this won't be much of a trouble. The problem begins when we have strings of at most 100 characters (as seen in the *Test Set 2* on Google Code Jam). That is $$ 2^{100} = 1\,267\,650\,600\,228\,229\,401\,496\,703\,205\,376 $$ possible highlightings. AND THAT IS AN AWFUL LOT. We don't have that much memory nor time! So this solution had to be discarted.