Documentation Index
Fetch the complete documentation index at: /llms.txt
Use this file to discover all available pages before exploring further.
Tested Python solution for LeetCode 1071 with 16 pytest cases. Generate a practice environment with lcpy.
lcpy gen -n 1071 # by problem number
lcpy gen -s gcd_of_strings # by problem name
s and t, we say “t divides s” if and only if s = t + 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.
Input: str1 = "ABCABC", str2 = "ABC"
Output: "ABC"
Input: str1 = "ABABAB", str2 = "ABAB"
Output: "AB"
Input: str1 = "LEET", str2 = "CODE"
Output: ""
1 <= str1.length, str2.length <= 1000str1 and str2 consist of English uppercase letters.from math import gcd
class Solution:
# Time: O(n + m) — concatenate + compare strings of total length n + m
# Space: O(n + m) — concatenated strings
def gcd_of_strings(self, str1: str, str2: str) -> str:
# If a common divisor exists, str1 and str2 must compose the same
# string regardless of concatenation order.
if str1 + str2 != str2 + str1:
return ""
# The largest common divisor has length = gcd of the two lengths.
gcd_len = gcd(len(str1), len(str2))
return str1[:gcd_len]
| Time | Space |
|---|---|
| O(n + m) — concatenate + compare strings of total length n + m | O(n + m) — concatenated strings |