Hello everyone, this video is for the CodeJam 2022 Round 1A, the first problem "Double or One Thing" Long story short: You are given a string of uppercase English letters. the length is from 1 up to 100. For each letter, you can double it or don’t change it at all. After some doubling, a new string is created. Each occurrence of the same letter can be doubled independently. Given a string, there are multiple strings that can be obtained as a result of this process, depending on the doubling choices. Among all of those strings, output the one that appears first in alphabetical order.

For example, “PEEL”, among all these 12 strings, "PEEEEL" appears first in alphabetical order. Suppose we have this string s, containing [c1, c2, c3, c4 ...]. In order to find the lexicographically smallest new string, we need to compare every adjacent pairs.

If c1 < c2, for example “ab”, compare “ab” and “aab”, we find out that “aab” is lexicographically smaller than “ab”, so double c1 will make the new string smaller. If c1 > c2, for example “ba”, compare “ba” and “bba”, we can see that doubling b makes the string bigger, so when c1 > c2, we do nothing.

What if they are the same? for example "cc", we have to compare it with c3. Using the same rules as before. If c1 < c3, we double c1, else don’t. And what if c1 also equals to c3? Then we have to compare it with c4… so we cannot decide by just comparing this pair.

So this technique is working partially, the first step is to divide the string into blocks of the same letters, for example, for this given string we create two variables "Letters" containing the letters showed up in the string in order, and "Count" is the occurrence of each letter in order. Then we compare each pair from the variable "Letters" instead of the original given string. U > S, so we just keep the letter we dont double it; S > M, we do the same.

M < Q, so we double M. There are two continuous M so we add 4 Ms Q < R, we double Q R > A, so we dont double R. And then add the final A. This string is the lexicographically smallest string we can find.

Okay lets take a look at the code. Start from adding a *, or any other characters as long as it’s not a letter, Separate the string into the blocks the same and the continuous characters. Then go through "Letters", compare every adjacent pairs. If the first letter is smaller than the second one, we double it. else we dont.

For the last letter, there’s no point of doubling it, just add it to the final result. If this letter showed several times in the end, then add it several times. Then convert this list into the string. The time complexity is O(N), and the space complexity is also O(N).

But dont stop it here, theres another solution.

When we compare the lexicographical order of two strings, we always start from the left side, first of each string, then the second, the third... so here’s another way of thinking, we start from the end instead of the beginning. For each letter, we have two options, double it or dont, we create two new strings, with this letter on the left, or with this letter doubled on the left, choose the smaller one. Repeat this process, until we reach the beginning. Then we find the lexicographically smallest string.

Here is the code. The code is much shorter, but the time complexity is not as good because of line 4. String is immutable, we are creating two new strings each time, this cost O(N). for loop is also O(N). Therefore, the time complexity is O(N^2) instead of O(N), space complexity is O(N) Thank you for watching.