dp-string-gcd.org

Greatest Common Divisor of Strings

From the Operation Code Slack

Problem statement:

For strings S and T, we say “T divides S” if and only if S = T + ... + T  (T concatenated with itself 1 or more times)
Return the largest string X such that X divides str1 and X divides str2.
```
Input: str1 = "ABCABC", str2 = "ABC"
Output: "ABC"

Input: str1 = "ABABAB", str2 = "ABAB"
Output: "AB"

Input: str1 = "LEET", str2 = "CODE"
Output: ""
```

Note:
• 1 <= str1.length <= 1000
• 1 <= str2.length <= 1000
• str1[i] and str2[i] are English uppercase letters.

str1	str2	output
ABCABC	ABC	ABC
ABABAB	ABAB	AB
ABABABB	ABAB
LEET	CODE

So lets enumerate conditions where you do get a match.

Firstly, we are always comparing the shorter string to the longer one. So lets make sure we know which is which

Then the most starightforward one is examples[0] where the shorter string is a proper subset of the longer one

There is also the situation on examples[1] where the full shorter string doesn’t fit into the the longer one an even amount of times but a shorter substring does.

It would seem that anything else would not be a match

def get_string_gcd(shorter, longer):
    if not shorter:
        return None
    if len(shorter) > len(longer):
        return get_string_gcd(longer, shorter)

Visualize moving thorugh examples[1]

Lets visualize things physically. We will consider examples[1]. We move through each char one by one, cycling back (starred below) on the short string if need be.

longer	shorter
A	A
B	B
A	A
B	B
A	*A
B	B

If we reach the end of the longer string then we have a match of the substring since last starred

Visualize moving through examples[2]

longer	shorter
A	A
B	B
A	A
B	B
A	*A
B	B
B	A!

Uh oh, we hit a situation where the next step on the left has no match on the right. This means there is no match

Back to the solution

Sounds like what we need to do is move through each string one by one cycling the shorter one but also noting what the most recent cycle is. itertools already has a cycle function but we want more than that. we don’t just want the next returned each time but the next and all within this current cycle. So lets implement that

def tracked_cycle(iterable):
    while True:
        current_cycle = []
        for x in iterable:
            current_cycle.append(x)
            yield (x, list(current_cycle)) #list needed since it passes by reference which is mutated

Ok, lets test that

from itertools import islice
for (_, s, _) in examples:
    print(
        list(islice(tracked_cycle(s), 0, 8))
    )

[('A', ['A']), ('B', ['A', 'B']), ('C', ['A', 'B', 'C']), ('A', ['A']), ('B', ['A', 'B']), ('C', ['A', 'B', 'C']), ('A', ['A']), ('B', ['A', 'B'])]
[('A', ['A']), ('B', ['A', 'B']), ('A', ['A', 'B', 'A']), ('B', ['A', 'B', 'A', 'B']), ('A', ['A']), ('B', ['A', 'B']), ('A', ['A', 'B', 'A']), ('B', ['A', 'B', 'A', 'B'])]
[('A', ['A']), ('B', ['A', 'B']), ('A', ['A', 'B', 'A']), ('B', ['A', 'B', 'A', 'B']), ('A', ['A']), ('B', ['A', 'B']), ('A', ['A', 'B', 'A']), ('B', ['A', 'B', 'A', 'B'])]
[('C', ['C']), ('O', ['C', 'O']), ('D', ['C', 'O', 'D']), ('E', ['C', 'O', 'D', 'E']), ('C', ['C']), ('O', ['C', 'O']), ('D', ['C', 'O', 'D']), ('E', ['C', 'O', 'D', 'E'])]

Ok, seems to work well. Also, hey! That’s a cool way of testing things isn’t it?

Alright, so now that we’ve got the above working its really a fairly straightforward matter of moving through each one at a time and testing the business logic

def get_string_gcd(shorter, longer):
    if not shorter:
        return None
    if len(shorter) > len(longer):
        return get_string_gcd(longer, shorter)
    current_cycle = []
    for ((s, current_cycle), l) in zip(tracked_cycle(shorter), longer):
        if s != l:
            return None
    return ''.join(current_cycle)

for (longer, shorter, desired) in examples:
    desired = desired or None
    gcd = get_string_gcd(shorter, longer)
    print(f'gcd({shorter}, {longer}) = {gcd}')
    if gcd != desired:
        print(f'FAILBOY! it should be {desired}\n')

gcd(ABC, ABCABC) = ABC
gcd(ABAB, ABABAB) = AB
gcd(ABAB, ABABABB) = None
gcd(CODE, LEET) = None