algoadvance

Leetcode 1071. Greatest Common Divisor of Strings

Problem Statement

Given two strings str1 and str2, return the largest string x such that x divides both str1 and str2.

Clarifying Questions

1. What does it mean for a string to divide another string?
   • A string x divides y if y is constructed by concatenating multiple copies of x.
2. What is the constraint on the length of the strings?
   • Both str1 and str2 have lengths in the range [1, 1000].
3. Does the input always contain valid strings?
   • Yes, the problem assumes valid input strings.

Strategy

To find the greatest common divisor (GCD) of two strings, follow these steps:

1. Verify if a GCD string exists:
   • A string x can be a valid GCD string if and only if str1 + str2 == str2 + str1 as string concatenation should align for a divisor to exist.
2. Use the mathematical GCD function:
   • If valid, determine the length of the potential GCD string using the GCD of the lengths of str1 and str2 (gcd(len(str1), len(str2))).
   • The GCD string will be the prefix of str1 (or str2, they are the same in this context) of length gcd(len(str1), len(str2)).

Code

Here’s the implementation of the described strategy in C++:

#include <iostream>
#include <string>
#include <algorithm>

class Solution {
public:
    std::string gcdOfStrings(std::string str1, std::string str2) {
        // Check if str1 + str2 == str2 + str1
        if (str1 + str2 != str2 + str1)
            return "";
        // Compute the GCD length
        int gcdLength = std::__gcd(str1.size(), str2.size());
        return str1.substr(0, gcdLength);
    }
};

// Usage Example
int main() {
    Solution sol;
    std::string str1 = "ABCABC";
    std::string str2 = "ABC";
    std::cout << "GCD of strings: " << sol.gcdOfStrings(str1, str2) << std::endl;
    return 0;
}

Time Complexity

• Concatenation and Comparison: str1 + str2 and str2 + str1 each take O(m + n) where m is the length of str1 and n is the length of str2.
• GCD Calculation: The time complexity of finding the GCD of two numbers is O(log(min(m, n))).
• Substring Extraction: This is O(g) where g is the GCD of m and n.

Thus, the overall time complexity is O(m + n), dominated by the string concatenation and comparison operations.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?