[LeetCode / C++] 1071. Greatest Common Divisor of Strings

1. Question

For two strings s and t, we say "t divides s" if and only if s = t + ... + t (i.e., t is concatenated with itself one or more times).

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

Example 1:

Input: str1 = "ABCABC", str2 = "ABC"
Output: "ABC"

Example 2:

Input: str1 = "ABABAB", str2 = "ABAB"
Output: "AB"

Example 3:

Input: str1 = "LEET", str2 = "CODE"
Output: ""

2. Thoughts

1) Return the GCD Length substring pattern if there exists a pattern between each other.
2) Check if pattern shows for all str1 and str2 to ensure the pattern is used throughout the whole word.

3. Tips learned

3.1. GCD

In C++, starting from C++17, the Standard Library provides a built-in function to calculate the Greatest Common Divisor (GCD) using the std::gcd() function, which is available in the <numeric> header.

Example: Using std::gcd() in C++17 or later

#include <iostream>
#include <numeric>  // For std::gcd

int main() {
    int a = 36;
    int b = 60;
    
    int gcd = std::gcd(a, b);
    
    std::cout << "GCD of " << a << " and " << b << " is: " << gcd << std::endl;  // Output: 12
    
    return 0;
}

Syntax:

std::gcd(a, b);

• a and b are integers (or any integer-like types like long or long long).
• It returns the greatest common divisor of a and b.

3.2. string compare in c++

• strcmp cannot be used with C++ std::string directly. To compare std::string objects, you should use the ==, <, >, etc., operators, which are overloaded for std::string.

  Example of comparing std::string:

  #include <iostream>
  #include <string>
  
  int main() {
      std::string str1 = "apple";
      std::string str2 = "banana";
  
      if (str1 == str2) {
          std::cout << "The strings are equal." << std::endl;
      } else if (str1 < str2) {
          std::cout << str1 << " is lexicographically smaller than " << str2 << "." << std::endl;
      } else {
          std::cout << str1 << " is lexicographically greater than " << str2 << "." << std::endl;
      }
  
      return 0;
  }

4. My solution

class Solution {
public:
    string gcdOfStrings(string str1, string str2) {

        string pattern = str1.substr(0,gcd(str1.length(), str2.length()));
        int patternLength = pattern.length();

        for (int i=0; i< str1.length() || i < str2.length() ; i+=patternLength){
            if ((i < str1.length() && pattern != str1.substr(i,patternLength)) 
            || (i < str2.length() && pattern != str2.substr(i,patternLength))) 
            return "";
        }

        return pattern;
    }
};

125/125 cases passed (0 ms)
Your runtime beats 100 % of cpp submissions
Your memory usage beats 67.46 % of cpp submissions (8.6 MB)

5. AI Solution and Improvements

Here’s an improved version of your code for finding the greatest common divisor (GCD) of two strings. I've made the following improvements:

1. Simplified the loop structure: We only need to compare the string concatenations directly without having to iterate and check substrings.
2. Early exit: Before performing any checks, we ensure that concatenating str1 and str2 in different orders produces the same result (i.e., str1 + str2 == str2 + str1). If this condition is not met, then there is no common divisor string.
3. Return the appropriate GCD substring: If the strings are valid for the operation, return the substring that represents the GCD based on the lengths of the input strings.

Here’s the improved code:

class Solution {
public:
    string gcdOfStrings(string str1, string str2) {
        // Check if str1 + str2 is the same as str2 + str1
        if (str1 + str2 != str2 + str1) {
            return "";
        }
        
        // Find the GCD of the lengths of the two strings
        int gcdLength = gcd(str1.length(), str2.length());
        
        // Return the substring of str1 from 0 to gcdLength, which is the gcd string
        return str1.substr(0, gcdLength);
    }
};

Explanation of improvements:

1. Check for common divisor pattern:

   • The condition str1 + str2 == str2 + str1 ensures that both strings share the same repeated pattern. If they do not, no common divisor exists, and we return "".

2. Use GCD of lengths:

   • Instead of manually iterating through both strings, the GCD of their lengths tells us the length of the largest string that can divide both. We can directly extract the substring from str1 using the result of gcd(str1.length(), str2.length()).

3. Simpler logic:

   • The loop is eliminated since the comparison of str1 + str2 and str2 + str1 serves as an early exit condition. If they are equal, we know the GCD substring is valid.

This solution is both cleaner and more efficient, leveraging string concatenation checks and GCD calculation to avoid unnecessary looping over the strings.