🚀 Day 10 of #90DaysOfDSA – Greatest Common Divisor of Strings

Hi everyone 👋, I'm Piyush Kumar, and welcome to Day 10 of my #90DaysOfDSA journey! Today I tackled a problem that perfectly blends string manipulation and math: Greatest Common Divisor of Strings.

---

🔍 Problem Statement

Given two strings str1 and str2, return the largest string x such that:

• str1 = x + x + ... + x (some number of times)

• str2 = x + x + ... + x (some number of times)

This is similar to finding the GCD (greatest common divisor) in math, but with strings.

---

🧠 Thought Process

To find the GCD of strings:

• First, ensure that both strings are composed of the same pattern.

• Then use the GCD of their lengths to find the smallest repeating unit that builds both.

---

✅ Python Code (My Version)

Here's the code I wrote:

pythonCopyEditclass Solution:
    def gcdOfStrings(self, str1: str, str2: str) -> str:
        # Check if both strings are composed of the same pattern
        if str1 + str2 != str2 + str1:
            return ''

        # Helper to compute GCD of two integers
        def compute_gcd(a, b):
            while b != 0:
                a, b = b, a % b
            return a

        # Get the GCD of the lengths
        len_gcd = compute_gcd(len(str1), len(str2))

        # Return the prefix of length GCD
        return str1[:len_gcd]

---

🧪 Example Outputs

pythonCopyEditgcdOfStrings("ABCABC", "ABC")      # Output: "ABC"
gcdOfStrings("ABABAB", "ABAB")     # Output: "AB"
gcdOfStrings("LEET", "CODE")       # Output: ""

---

🔍 Why str1 + str2 != str2 + str1?

If both strings are made up of the same repeating pattern, concatenating them in either order should result in the same string.

For example:

• "ABCABC" + "ABC" → "ABCABCABC"

• "ABC" + "ABCABC" → "ABCABCABC"

If not equal, they can't share a common base pattern — so return "".

---

🧠 Key Takeaways

• Use string concatenation to test pattern compatibility.

• The Euclidean algorithm is a powerful tool for more than just numbers.

• The problem is a great mix of pattern recognition, math, and string manipulation.

---

📎 My Code on GitHub

🔗 View the full solution here

---

🧵 Final Thoughts

This problem was a refreshing mix of logic and implementation. It reminded me how classic algorithms like GCD can be applied creatively in different domains — even with strings!

Thanks for reading! Stay tuned for Day 11!
— Piyush Kumar