Array / String· 15 min

Greatest Common Divisor of Strings

LeetCode #1071 · Easy · Interactive step-by-step visualization

Setup

Example inputstr1 = "ABCABC", str2 = "ABC"
Step 1 / 7

Current step

1 / 7

Start by checking whether both strings can be built from one repeating base.

Step log

str1

ABCABC

str2

ABC

str1 + str2

ABCABCABC

str2 + str1

ABCABCABC

a

6

b

3

a mod b

—

Active
Comparing
Committed
Rejected or blocked
greatest-common-divisor-of-strings.java
1public String gcdOfStrings(String str1, String str2) {
2    if (!(str1 + str2).equals(str2 + str1))
3        return "";
4    int a = str1.length(), b = str2.length();
5    while (b != 0) {
6        int next = a % b;
7        a = b; b = next;
8    }
9    return str1.substring(0, a);
10}
● Java
Time
O(n + m)
Space
O(n + m)
Pattern
array scan
Frames
7
2 / 75