Change language

Google Code Jam 2022 Round 1A | Double or One Thing | Python

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.

Shop

Learn programming in R: courses

\$

Best Python online courses for 2022

\$

Best laptop for Fortnite

\$

Best laptop for Excel

\$

Best laptop for Solidworks

\$

Best laptop for Roblox

\$

Best computer for crypto mining

\$

Best laptop for Sims 4

\$

Latest questions

NUMPYNUMPY

Common xlabel/ylabel for matplotlib subplots

NUMPYNUMPY

How to specify multiple return types using type-hints

NUMPYNUMPY

Why do I get "Pickle - EOFError: Ran out of input" reading an empty file?

NUMPYNUMPY

Flake8: Ignore specific warning for entire file

NUMPYNUMPY

glob exclude pattern

NUMPYNUMPY

How to avoid HTTP error 429 (Too Many Requests) python

NUMPYNUMPY

Python CSV error: line contains NULL byte

NUMPYNUMPY

csv.Error: iterator should return strings, not bytes

Wiki

Python | How to copy data from one Excel sheet to another

Common xlabel/ylabel for matplotlib subplots

Check if one list is a subset of another in Python

How to specify multiple return types using type-hints

Printing words vertically in Python

Python Extract words from a given string

Cyclic redundancy check in Python

Finding mean, median, mode in Python without libraries