Problem editorial

Greatest Common Divisor of Strings

EasyString Manipulation PatternsStringMathNumber Theory

Greatest Common Divisor of Strings: the approach in brief

The problem

A string x divides another string y when y can be formed by concatenating one or more copies of x. A common divisor string of str1 and str2 must divide both parameters.

Pattern

Greatest Common Divisor of Strings is a String Manipulation Patterns problem, in the Repeated Substring Pattern Detection subpattern. The pattern covers palindrome checking, anagram detection, pattern matching, and string conversion

Approach outline

Any valid common divisor must generate both strings by repetition, so the two inputs must have compatible repeating structure.
Compare the strings formed by concatenating `str1` then `str2` and `str2` then `str1`.
If those concatenations differ, no non-empty common divisor can exist.

Complexity

The reference solution runs in O(|str1| + |str2|) time and O(|str1| + |str2|) auxiliary space space.

The full editorial is part of Pro

It explains the core insight, the complexity analysis and the common mistakes, with a worked solution.

Unlock the full editorial with Pro Solve it first, free

Practise Greatest Common Divisor of Strings and the problems around it

Greatest Common Divisor of Strings is a String Manipulation Patterns problem, in the Repeated Substring Pattern Detection subpattern. Once the approach above makes sense, write it yourself and then work through the neighbouring problems that reuse it.

Greatest Common Divisor of Strings