Learn
Practice
Interview
Resources
Newsletter
F
Toggle theme
0
F
0
Toggle menu
Animations
← Back to All Animations
Greatest Common Divisor of Strings
Bookmark
Input
Standard
Longer GCD
No GCD
Single Char
Equal
Custom
str1
=
ABCABC
,
str2
=
ABC
str1
A
B
C
A
B
C
str2
A
B
C
A divisor string must tile both str1 and str2
str1
A
B
C
A
B
C
str2
A
B
C
A divisor string must tile both str1 and str2
str1+str2
A
B
C
A
B
C
A
B
C
str2+str1
A
B
C
A
B
C
A
B
C
str1+str2 = str2+str1 → a divisor exists
str1
A
B
C
A
B
C
str2
A
B
C
a
6
b
3
gcd(len1, len2) = gcd(6, 3)
str1
A
B
C
A
B
C
str2
A
B
C
a
3
b
0
6 mod 3 =
0
→ a=3, b=0
str1
A
B
C
A
B
C
str2
A
B
C
a
3
b
0
b = 0 → gcd =
3
str1
A
B
C
A
B
C
str2
A
B
C
str1
A
B
C
A
B
C
str2
A
B
C
result = "ABC"
str1 = "ABC" × 2 str2 = "ABC" × 1
algo
master
.
io
Step:
Start: find the GCD string of "ABCABC" and "ABC"
0 / 6
Input
Standard
Longer GCD
No GCD
Single Char
Equal
Custom
str1
=
ABCABC
,
str2
=
ABC
0 / 6
algo
master
.
io
Step:
Start: find the GCD string of "ABCABC" and "ABC"
