Greatest Common Divisor of Strings: A Fun Coding Challenge

Do you remember the fun of sharing?

Imagine you're at a picnic with your friends, and everyone brings something to share. Some bring sandwiches, others bring snacks, and there's always that one friend who brings a huge cake! But here's the tricky part: how do you make sure everyone gets an equal share?

It reminds me of a story about Steve Jobs, the co-founder of Apple. He believed in simplicity and fairness. When creating products, he always asked, "How can we make this simple for everyone?" This idea of fairness and simplicity is not just important in life but also in coding.

Today, we're going to explore a coding challenge called the "Greatest Common Divisor of Strings." It might sound complex, but it's just like making sure everyone gets an equal share of that cake.

Problem statement: Finding the greatest common divisor of strings

Let’s break down the problem. You have two strings, and you need to find the greatest string that can divide both of them equally. In simpler terms, you’re looking for the largest string that can be repeated to form both original strings.

For example, consider these two strings:

• String 1: "ABABAB"
• String 2: "ABAB"

The greatest common divisor of these strings is "AB." Why? Because "AB" can be repeated to form both "ABABAB" and "ABAB."

Just like dividing a cake into equal slices, we need to find the string that evenly divides both original strings.

Sample input and output

Here’s what this looks like:

1Input: str1 = "ABCABC", str2 = "ABC"
2Output: "ABC"
3
4Input: str1 = "ABABAB", str2 = "ABAB"
5Output: "AB"
6
7Input: str1 = "LEET", str2 = "CODE"
8Output: ""

Explanation:

• The string "ABC" can be repeated to create both "ABCABC" and "ABC."

Brainstorming ideas to solve

Before we start coding, let's think about some ideas on how to solve the problem. Here are a few things to consider:

• Understand the Problem:
  • We need to find a common piece of the string that can be repeated to make both original strings.
  • This common piece should be the biggest one that can work for both strings.
• Compare the Strings:
  • We can check if the two strings can be combined in any order (like str1 + str2 and str2 + str1).
  • If they can be combined in the same way, it means they might have a common divisor.
• Think About String Lengths:
  • The common piece of the string should have a length that is a divisor (a number that divides without leaving a remainder) of both original string lengths.
  • For example, if one string is 6 characters long and the other is 9 characters long, the common piece might be 3 characters long because 3 is a divisor of both 6 and 9.
• Use GCD (Greatest Common Divisor):
  • The GCD of the lengths of the two strings can help us find out how long the common piece should be.
  • Once we know this length, we can check if the starting part of the strings with this length can be repeated to form the original strings.
• Check and Compare:
  • After finding the common piece using the GCD, we should check if repeating this piece can make both original strings.
  • If it can, then this piece is the greatest common divisor of the strings. If not, there’s no common divisor.

Pseudo code

Let’s break this down into a simple, step-by-step plan:

• Find the lengths of both strings.
• Check if one string is longer than the other.
• Find the greatest common divisor (GCD) of the two lengths.
• Use the GCD to extract a substring from the beginning of the longer string.
• Check if this substring, when repeated, forms both original strings.
• If yes, return this substring as the answer.
• If no common substring works, return an empty string.

Method 1: Brute force approach

The brute force approach involves trying out all possible substrings and checking if they can divide both original strings equally.

Python code:

1import math
2
3def gcd_of_strings(str1, str2):
4    # Step 1: Check if str1 + str2 equals str2 + str1
5    if str1 + str2 != str2 + str1:
6        return ""
7    
8    # Step 2: Find the GCD of the lengths of the two strings
9    gcd_length = math.gcd(len(str1), len(str2))
10    
11    # Step 3: Return the substring from the start to gcd_length
12    return str1[:gcd_length]
13
14# Sample input
15str1 = "ABCABC"
16str2 = "ABC"
17# Expected output: "ABC"
18print("Output:", gcd_of_strings(str1, str2))

Explanation:

• Check Compatibility: First, we check if combining the strings in different orders gives the same result. If not, they don’t have a common divisor string.
• Find GCD of Lengths: We use Python's math.gcd() function to find the greatest common divisor of the string lengths.
• Return Substring: Finally, we return the substring from the start of the first string up to the GCD length.

Java code:

1import java.util.*;
2
3public class GCDOfStrings {
4    public static String gcdOfStrings(String str1, String str2) {
5        // Step 1: Check if str1 + str2 equals str2 + str1
6        if (!(str1 + str2).equals(str2 + str1)) {
7            return "";
8        }
9        
10        // Step 2: Find the GCD of the lengths of the two strings
11        int gcdLength = gcd(str1.length(), str2.length());
12        
13        // Step 3: Return the substring from the start to gcd_length
14        return str1.substring(0, gcdLength);
15    }
16    
17    private static int gcd(int a, int b) {
18        if (b == 0) {
19            return a;
20        } else {
21            return gcd(b, a % b);
22        }
23    }
24
25    public static void main(String[] args) {
26        String str1 = "ABCABC";
27        String str2 = "ABC";
28        // Expected output: "ABC"
29        System.out.println("Output: " + gcdOfStrings(str1, str2));
30    }
31}

Explanation:

• Check Compatibility: We first check if the strings can be combined in any order to produce the same result.
• Find GCD of Lengths: We calculate the GCD of the string lengths using a helper function.
• Return Substring: We return the substring from the first string that corresponds to this GCD length.

C++ code:

1#include <iostream>
2#include <algorithm>
3
4std::string gcdOfStrings(std::string str1, std::string str2) {
5    // Step 1: Check if str1 + str2 equals str2 + str1
6    if (str1 + str2 != str2 + str1) {
7        return "";
8    }
9    
10    // Step 2: Find the GCD of the lengths of the two strings
11    int gcdLength = std::gcd(str1.length(), str2.length());
12    
13    // Step 3: Return the substring from the start to gcd_length
14    return str1.substr(0, gcdLength);
15}
16
17int main() {
18    std::string str1 = "ABCABC";
19    std::string str2 = "ABC";
20    // Expected output: "ABC"
21    std::cout << "Output: " << gcdOfStrings(str1, str2) << std::endl;
22    
23    return 0;
24}

Explanation:

• Check Compatibility: We verify if the combined strings produce the same result in different orders.
• Find GCD of Lengths: The GCD of the lengths is calculated using C++’s std::gcd function.
• Return Substring: We extract the substring that corresponds to this GCD length and return it.

Method 2: Optimal approach using string properties

While the brute force approach is straightforward, we can make our solution more efficient by focusing on the properties of the strings.

Python code:

1import math
2
3def gcd_of_strings(str1, str2):
4    # Step 1: Check if str1 + str2 equals str2 + str1
5    if str1 + str2 != str2 + str1:
6        return ""
7    
8    # Step 2: Find the GCD of the lengths of the two strings
9    gcd_length = math.gcd(len(str1), len(str2))
10    
11    # Step 3: Return the substring from the start to gcd_length
12    return str1[:gcd_length]
13
14# Sample input
15str1 = "ABCABC"
16str2 = "ABC"
17# Expected output: "ABC"
18print("Output:", gcd_of_strings(str1, str2))

Explanation:

• Optimization: This solution is already optimized as it uses string properties and mathematical functions to avoid unnecessary operations.

Conclusion

Just like Steve Jobs believed in making things simple and fair, finding the Greatest Common Divisor of Strings is about simplifying the problem and ensuring that everything divides equally.

By understanding the problem and breaking it down into smaller steps, we can solve it efficiently. Whether you use Python, Java, or C++, the approach remains the same: focus on the fundamentals, keep it simple, and always aim for fairness.

Coding is not just about writing code; it’s about thinking clearly, solving problems, and making sure everyone gets an equal share of the cake. So, keep practicing, keep learning, and remember that simplicity often leads to the best solutions!