# Solving Leetcode Interviews in Seconds with AI: Greatest Common Divisor of Strings


	# Introduction
	In this blog post, we will explore how to solve the LeetCode problem "1071" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like [Chatmagic](https://www.chatmagic.app), we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

	# Problem Statement
	> For two strings 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.   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: ""    Constraints:  1 <= str1.length, str2.length <= 1000 str1 and str2 consist of English uppercase letters.  

	# Explanation
	Here's the breakdown of the solution:

*   **GCD Length:** The length of the greatest common divisor (GCD) string must divide the lengths of both input strings. We find the GCD of the lengths of `str1` and `str2`.
*   **Substring Check:**  We extract a substring of `str1` with the GCD length. This substring is our candidate for the GCD string.
*   **Divisibility Verification:** We verify if this candidate string divides both `str1` and `str2`. If it does, we return it; otherwise, we return an empty string.

*   **Runtime Complexity:** O(m + n) where m and n are the lengths of str1 and str2, due to the gcd calculation and the string divisibility checks.
*   **Storage Complexity:** O(1), constant extra space.

	
	# Code
	```python
	def gcdOfStrings(str1: str, str2: str) -> str:
    """
    For two strings 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.
    """

    def gcd(a: int, b: int) -> int:
        """
        Calculates the greatest common divisor of two integers using the Euclidean algorithm.
        """
        while b:
            a, b = b, a % b
        return a

    def divides(s: str, t: str) -> bool:
        """
        Checks if string t divides string s.
        """
        if len(s) % len(t) != 0:
            return False
        num_repeats = len(s) // len(t)
        return t * num_repeats == s

    len_gcd = gcd(len(str1), len(str2))
    candidate = str1[:len_gcd]

    if divides(str1, candidate) and divides(str2, candidate):
        return candidate
    else:
        return ""
	```