LeetCode Python Solutions: 1071. Greatest Common Divisor of Strings #python #coding #leetcode

ZeroStress LeetCode Python Solutions: 1071. Greatest Common Divisor of Strings #python #leetcode

Twitter: https://twitter.com/QiaoLiuCiao

Welcome to our tutorial on solving the 'Greatest Common Divisor of Strings' problem from LeetCode. In this tutorial, we will dive into a fascinating problem that involves finding the largest common divisor string between two given strings. This problem not only challenges our understanding of strings but also requires us to think about patterns and divisibility.

Throughout this tutorial, we will explore a solution that offers an efficient approach to solve the problem. Our solution, Solution 1, is based on the insight that if a common divisor string exists between two strings, both strings can be formed by repeating this common divisor.

We will walk through each line of code, discussing the syntax, mechanism, algorithm, and logic behind the scene. We'll explain the key steps, such as checking the concatenation condition, calculating the greatest common divisor (gcd) of string lengths, and extracting the corresponding substring. Additionally, we will analyze the time and space complexity of our solution to understand its efficiency.

By the end of this tutorial, you will have a solid understanding of the problem statement, the approach we took, and the rationale behind each line of code in Solution 1. You'll also gain insights into the time and space complexity of our solution.

Whether you're a beginner looking to sharpen your problem-solving skills or an experienced programmer interested in tackling LeetCode problems, this tutorial is designed to help you enhance your understanding of strings, pattern matching, and algorithmic thinking.

The approach of Solution can be summarized as follows:

First, the solution checks if the concatenation of str1 and str2 is equal to the concatenation of str2 and str1. This step ensures that both str1 and str2 can be formed by repeating the same string.

If the condition is not satisfied, it means there is no common divisor string that can divide both str1 and str2. In this case, the solution returns an empty string.

If the condition is satisfied, the solution proceeds to calculate the greatest common divisor (gcd) of the lengths of str1 and str2 using the gcd function from the math module. The gcd represents the length of the largest common divisor string.

Finally, the solution returns a substring of str1 starting from index 0 and with a length equal to the calculated gcd. This substring represents the largest string that can divide both str1 and str2.

The overall approach of Solution involves checking the concatenation condition, calculating the gcd of string lengths, and extracting the corresponding substring. This approach efficiently finds the largest common divisor string between str1 and str2 when it exists.

Time Complexity:

The condition str1 + str2 != str2 + str1 is checked in constant time, as it involves concatenating the strings and comparing them. This operation has a time complexity of O(N), where N is the total length of the input strings str1 and str2.

The gcd function from the math module is called with the lengths of str1 and str2, which takes constant time as well.

Overall, the time complexity of Solution 1 is O(N), where N is the total length of the input strings str1 and str2.

Space Complexity:

The space complexity of Solution 1 is O(1) because it does not use any additional data structures that grow with the input size. The space usage remains constant throughout the execution.
In summary, Solution 1 has a time complexity of O(N) and a space complexity of O(1). It provides an efficient approach to finding the largest common divisor string between str1 and str2.


The math module in Python is a built-in module that provides mathematical functions and constants. It contains various functions and tools for mathematical operations, such as trigonometric functions, exponential functions, logarithmic functions, and more.

The gcd function specifically stands for "greatest common divisor." It is a mathematical function that calculates the largest positive integer that divides two or more numbers without leaving a remainder. The gcd function is commonly used in number theory and various mathematical algorithms.

In Python, the gcd function is part of the math module. By importing gcd from the math module (from math import gcd), you can directly use this function to calculate the greatest common divisor of two integers.


00:00 Code
02:00 Main
11:00 End