Find the Greatest Common Divisor of Strings | Leetcode 75 Explained #Python #Leetcode #CodingShorts

🚀 Leetcode 1071: Greatest Common Divisor of Strings – Fully Explained with Python Solution!

In this video, we tackle the "Greatest Common Divisor of Strings" problem from Leetcode 75, breaking it down step by step for easy understanding. This problem is based on string manipulation and the Euclidean Algorithm. Let's go through the solution and understand how we can efficiently determine the largest string that evenly divides two given strings!

💡 Problem Statement:

Given two strings str1 and str2, we need to return the largest string X such that X can be concatenated multiple times to form both str1 and str2. If no such string exists, return an empty string ("").

🔍 Step-by-Step Explanation:

1️⃣ Check for a Valid Divisor:

If str1 + str2 != str2 + str1, this means the strings are not made of the same repeating pattern, and there is no common divisor. So, we return "".

2️⃣ Find the Greatest Common Divisor (GCD) of the Lengths:

We compute gcd(len(str1), len(str2)) using the Euclidean Algorithm, which is an efficient way to find the greatest common divisor of two numbers.
If a % b == 0, then b is the GCD. Otherwise, we continue with gcd(b, a % b).

3️⃣ Extract the Common Prefix:

The GCD of the lengths tells us the maximum length of the repeating substring that could be a valid divisor.
The first gcd_length characters of str1 give us the answer.

✅ Code Implementation in Python:

class Solution:
def gcd(self, a, b):
while b:
a, b = b, a % b
return a

def gcdOfStrings(self, str1, str2):
# If concatenation of both in different orders is not equal, return ""
if str1 + str2 != str2 + str1:
return ""

# Find the GCD of lengths

# Return the common prefix
return str1[:gcd_length]

📌 Example Walkthrough:

✅ Example 1:

Input: str1 = "ABCABC", str2 = "ABC"
Output: "ABC"
Explanation: "ABC" is the largest string that repeats in both str1 and str2.

✅ Example 2:

Input: str1 = "ABABAB", str2 = "ABAB"
Output: "AB"
Explanation: "AB" is the largest repeating string in both words.

✅ Example 3:

Input: str1 = "LEET", str2 = "CODE"
Output: ""
Explanation: Since "LEET" + "CODE" != "CODE" + "LEET", there is no valid divisor.

🔥 Why is This Approach Efficient?

✅ Time Complexity: O(log(min(len(str1), len(str2)))) (due to GCD calculation)

✅ Space Complexity: O(1) (only uses a few variables)

✅ Uses String Properties + Mathematical GCD Concept

🎯 Must Watch If You Want To:

✅ Improve your string manipulation skills

✅ Learn GCD concepts applied to strings

✅ Solve more Leetcode 75 problems for coding interviews