Greatest Common Divisor Of Strings - Leetcode Solution

Problem Description:

Given two strings str1 and str2, return the largest string x such that x divides both str1 and str2.

A string x divides a string y if there exists a string z such that y = x + z.

Example 1:

Input: str1 = "ABCABC", str2 = "ABC" Output: "ABC" Example 2:

Input: str1 = "ABABAB", str2 = "ABAB" Output: "AB"

Solution:

To find the GCD of two strings s1 and s2, we need to keep checking for the common divisors of both the strings from their start.

Steps to solve the problem:

1. If both strings are empty, return an empty string.

2. If either of the strings is empty, return the other string.

3. Check if the length of s1 is less than s2.

If it is, swap s1 and s2.

4. Check if s1 is divisible by s2.

If it is, return s2.

5. Otherwise, divide s1 by s2 and subtract the remainder from s1.

6. Repeat the steps 3 to 5 until s1 is empty or s2 is empty.

7. If either of the strings is empty, return the other string.

Let's implement this algorithm in python:

def gcdOfStrings(str1: str, str2: str) -> str: if len(str1) == 0 or len(str2) == 0: return '' if len(str1) < len(str2): str1, str2 = str2, str1 if str1 == str2: return str1

if str1.startswith(str2):
    return gcdOfStrings(str1[len(str2):], str2)

return ''

Time Complexity:

The time complexity of the above solution is O(n^2), where n is the length of the longest string.

Space Complexity:

The space complexity of the above solution is O(n), where n is the length of the longest string.

1