{{ message }}

Instantly share code, notes, and snippets.

# togakangaroo/dp-string-gcd.org

Last active Oct 14, 2019

### 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.```
str1str2output
ABCABCABCABC
ABABABABABAB
ABABABBABAB
LEETCODE

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` where the shorter string is a proper subset of the longer one

There is also the situation on `examples` 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`

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

longershorter
AA
BB
AA
BB
A*A
BB

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

#### Visualize moving through `examples`

longershorter
AA
BB
AA
BB
A*A
BB
BA!

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
```