Skip to main content

1071. Greatest Common Divisor of Strings

easy

Find the longest string x such that x divides both str1 and str2 (where 'divides' means repeated concatenation). A beautiful application of Euclid's algorithm to strings — with a one-line correctness check.

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

For two strings s and t, we say 't divides s' if and only if s = t + t + t + ... + t (i.e., t is concatenated with itself one or more times). Given two strings str1 and str2, return the largest string x such that x divides both str1 and str2.

Constraints

  • 1 <= str1.length, str2.length <= 1000
  • str1 and str2 consist of English uppercase letters.

Examples

Example 1

Input
str1 = "ABCABC", str2 = "ABC"
Output
"ABC"

Example 2

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

Example 3

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

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

If a divisor x exists, then str1 + str2 must equal str2 + str1 — both concatenations decompose into copies of x.

Hint 2

Conversely, if str1 + str2 != str2 + str1, no common divisor exists. Return empty string.

Hint 3

When a divisor exists, its length divides both len(str1) and len(str2). The LARGEST such length is gcd(len(str1), len(str2)).

Hint 4

Take the prefix of str1 of length gcd(len(str1), len(str2)). That's the answer.

Solution approach

Reveal approach

Apply Euclid's algorithm to lengths. Step 1: check concat equality — if str1 + str2 != str2 + str1, no common divisor exists, return empty string. Step 2: compute g = gcd(len(str1), len(str2)) using the standard Euclidean algorithm. Step 3: return str1[0:g] (or equivalently str2[0:g]). The concat-equality test is the elegant bit: it's both necessary and sufficient for a common divisor to exist. Once existence is confirmed, the largest divisor length is exactly the gcd of the lengths. O(m + n) time for the concat checks and gcd, O(m + n) space for the concat strings.

Complexity

Time
O(m + n)
Space
O(m + n)

Related patterns

  • math
  • string-scan
  • euclidean-algorithm

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google

More Math practice problems

See all Math problems →