Two pointers into one table

When the third quantity you thought you needed is implied by the other two.

Why it works

The third number is not free

Every character of the result comes from exactly one source, so the amount of result built is always the sum of the two amounts consumed. The third index is determined by the first two and carries no information.

So the state is two numbers and the table is two-dimensional. Noticing that a candidate index is implied by the others is a general move worth looking for, and it is the difference here between a cubic table and a quadratic one.

Below, every pair of consumed amounts is listed with the result position it implies, which is the whole content of that observation.

1first, second, result = "abc", "de", "adbce"2 3for i in range(len(first) + 1):4    for j in range(len(second) + 1):5        if i + j == 0 or i + j > len(result):6            continue7        print(f"consumed {i} of '{first}' and {j} of '{second}'"8              f" -> next to match is result[{i + j - 1}] = '{result[i + j - 1]}'")

No third index anywhere. The result position is arithmetic on the two that are already there.

Predict the output· 5 min

Predict the output: why a greedy walk is not enough

Both sources start with the same character, so a walk that always prefers the first source has to guess. Type the two lines it prints.

Python

1first, second, result = "ab", "aab", "aaabb"[:4]2 3print("result to build:", result)4print("both sources start with:", first[0], second[0], "-> the first step is a guess")

Printed output

Problem· 30 min

Interleaving String

Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.

1first, second, result = "abc", "de", "adbce"2 3for i in range(len(first) + 1):4 for j in range(len(second) + 1):5 if i + j == 0 or i + j > len(result):6 continue7 print(f"consumed {i} of '{first}' and {j} of '{second}'"8 f" -> next to match is result[{i + j - 1}] = '{result[i + j - 1]}'")