09 Sept 2026•Easy•Go / Python / TypeScript

Greatest Common Divisor of Strings

Find the longest string that can be repeated to construct each of two strings.

Compatible strings commute under concatenation. When they do, the answer is the prefix whose length is the gcd of their lengths.

Complexity

O(n + m) time and O(n + m) temporary string space.

Solution files

Go•greatest-common-divisor-of-strings/solution.go

package main

func gcdOfStrings(str1 string, str2 string) string {
	if str1+str2 != str2+str1 {
		return ""
	}
	a, b := len(str1), len(str2)
	for b != 0 {
		a, b = b, a%b
	}
	return str1[:a]
}

Python•greatest-common-divisor-of-strings/solution.py

from math import gcd


class Solution:
    def gcdOfStrings(self, str1: str, str2: str) -> str:
        return str1[:gcd(len(str1), len(str2))] if str1 + str2 == str2 + str1 else ""

TypeScript•greatest-common-divisor-of-strings/solution.ts

function gcdOfStrings(str1: string, str2: string): string {
  if (str1 + str2 !== str2 + str1) return "";
  const gcd = (a: number, b: number): number => b === 0 ? a : gcd(b, a % b);
  return str1.slice(0, gcd(str1.length, str2.length));
}