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 Alex Chen, 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

Practice these live with InterviewChamp.AI

Drill Greatest Common Divisor of Strings and Math problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →