[MEDIUM] #1072 - Flip Columns For Maximum Number of Equal Rows

[hackdartstorm]

🎯 Problem: Greatest Common Divisor of Strings

📖 The Real Problem

You are given two strings str1 and str2. Your task is to find the largest string that can divide both strings completely.

What does "divide" mean?

• A string t divides string s if s can be formed by concatenating t with itself one or more times
• Example: "ABC" divides "ABCABC" because "ABC" + "ABC" = "ABCABC"

The Challenge:

• Need to find the GCD string that divides BOTH input strings
• The GCD string must be the largest possible
• Must verify that the GCD actually works for both strings
• Handle cases where no common divisor exists

Why this problem exists:

• Tests understanding of string patterns and periodicity
• Combines mathematical GCD concepts with string manipulation
• Requires recognizing repeating patterns in strings
• Real-world applications in data compression and pattern recognition

💡 Why This Matters

Real-world applications:

• Data Compression - Finding repeating patterns for compression algorithms
• Signal Processing - Identifying periodic signals in data
• DNA Sequence Analysis - Finding repeating genetic patterns
• Text Processing - Pattern matching and string normalization
• Cryptography - String-based encryption patterns

Skills you'll develop:

• ✅ String manipulation and pattern recognition
• ✅ Mathematical GCD algorithm application
• ✅ String concatenation verification
• ✅ Algorithm optimization
• ✅ Edge case handling

📋 Contributor Tasks

Step 1: Understand the Problem

1. Read the problem statement carefully
2. Work through examples manually on paper
3. Understand what "string division" means
4. Identify when no solution exists

Step 2: Plan Your Approach

Key Insight:

• If str1 + str2 != str2 + str1, then no common divisor exists
• The length of GCD string must be GCD of the lengths of str1 and str2
• Check if the prefix of GCD length works for both strings

Mathematical Approach:

1. Check if str1 + str2 == str2 + str1
2. If not, return "" (no solution)
3. If yes, find GCD of lengths
4. Return prefix of that length

Step 3: Implement the Solution

1. Check concatenation equality
2. Calculate GCD of string lengths
3. Extract prefix of GCD length
4. Verify it divides both strings
5. Return the result

Step 4: Test Your Solution

1. Test with strings that have common divisor
2. Test with strings that don't have common divisor
3. Test with identical strings
4. Test with one string being multiple of another
5. Test edge cases (empty strings, single characters)

✅ Expected Outcome

Function Signature:

def gcdOfStrings(str1: str, str2: str) -> str:
    """
    Find the largest string that divides both str1 and str2.
    
    Args:
        str1: First input string
        str2: Second input string
    
    Returns:
        str: Largest common divisor string, or "" if none exists
    
    Example:
        >>> gcdOfStrings("ABCABC", "ABC")
        "ABC"
    """

Expected Behavior:

• ✅ Returns largest string that divides both inputs
• ✅ Returns "" when no common divisor exists
• ✅ Handles strings of different lengths
• ✅ Handles identical strings correctly
• ✅ Efficient implementation

Example Test Cases:

# Test 1: Basic example with common divisor
gcdOfStrings("ABCABC", "ABC")  # Returns: "ABC"
# ABC divides ABCABC (ABC+ABC) and ABC (ABC)

# Test 2: No common divisor
gcdOfStrings("LEET", "CODE")  # Returns: ""
# No string divides both

# Test 3: One is multiple of other
gcdOfStrings("ABABAB", "ABAB")  # Returns: "AB"
# AB divides both strings

# Test 4: Identical strings
gcdOfStrings("ABC", "ABC")  # Returns: "ABC"

# Test 5: Complex pattern
gcdOfStrings("ABABABAB", "ABAB")  # Returns: "ABAB"

📚 Additional Context & References

Understanding String Division

String Division Definition:
String t divides string s if:

• s = t + t + t + ... + t (n times, where n >= 1)
• Equivalently: s = t * n for some positive integer n

Examples:

"ABC" divides "ABCABC"     ✓ (ABC * 2)
"ABC" divides "ABCABCABC"  ✓ (ABC * 3)
"AB" divides "ABAB"        ✓ (AB * 2)
"AB" does NOT divide "ABC"  ✗

Solution Approach

Optimal Solution:

import math

def gcdOfStrings(str1: str, str2: str) -> str:
    # Key insight: if str1 + str2 != str2 + str1, no solution
    if str1 + str2 != str2 + str1:
        return ""
    
    # Find GCD of lengths
    gcd_length = math.gcd(len(str1), len(str2))
    
    # Return prefix of GCD length
    return str1[:gcd_length]

Why This Works:

1. Concatenation Check: If str1 and str2 share a common divisor, then str1+str2 must equal str2+str1
2. GCD of Lengths: The largest common divisor string must have length = GCD(len(str1), len(str2))
3. Prefix Extraction: The GCD string is the prefix of either string with GCD length

Hints (Use Only If Stuck!)

💡 Hint 1

Think about what happens when you concatenate the strings in different orders. What does it mean if str1+str2 == str2+str1?

💡 Hint 2

The length of the GCD string must divide both string lengths. What mathematical operation finds the largest common divisor of two numbers?

💡 Hint 3

If a common divisor exists, it must be a prefix of both strings. Which prefix length should you try?

Complexity Analysis

Time Complexity: O(n + m)

• n = len(str1), m = len(str2)
• Concatenation check: O(n + m)
• GCD calculation: O(log(min(n, m)))
• String slicing: O(gcd_length)
• Overall: O(n + m)

Space Complexity: O(n + m)

• For string concatenation check
• Could be optimized to O(1) with careful implementation

Edge Cases to Consider

1. No common divisor: Return ""
2. Identical strings: Return the string itself
3. One empty string: Handle gracefully
4. Single character strings: Works correctly
5. Prime length strings: May have no common divisor

Related Problems

Once you solve this, try:

• GCD of Two Numbers - Mathematical foundation
• Repeated String Match - Similar pattern matching
• Detect Pattern in String - String periodicity
• Longest Common Prefix - String comparison

Helpful Resources

• Mathematical GCD
• String Periodicity
• Python math.gcd
• LeetCode 1071 - Greatest Common Divisor of Strings

📝 Notes

• Input strings contain only uppercase English letters
• String lengths: 1 to 1000
• Return "" (empty string) when no solution exists
• The GCD string must divide BOTH strings completely
• Concatenation check is necessary and sufficient

---

Ready to contribute?

1. Fork the repository
2. Create your solution file
3. Test with provided examples
4. Submit a pull request!

File Location: exercises/1000_programs/medium/1071_gcd_of_strings.py

🚀 Happy coding!