1071. Greatest Common Divisor of Strings

Approach 1: Brute Force

• Time: $O(\min(|\texttt{str1}|, |\texttt{str2}|) \cdot (|\texttt{str1}| + |\texttt{str2}|))$
• Space: $O(|\texttt{str1}| + |\texttt{str2}|)$

C++JavaPython

class Solution {
 public:
  string gcdOfStrings(string str1, string str2) {
    for (int sz = min(str1.length(), str2.length()); sz > 0; --sz)
      if (isDivisible(str1, str2, sz))
        return str1.substr(0, sz);
    return "";
  }

 private:
  // Returns true if str1 and str2 are divisible by str1[0..sz).
  bool isDivisible(const string& str1, const string& str2, int sz) {
    if (str1.length() % sz > 0 || str2.length() % sz > 0)
      return false;
    const string gcd = str1.substr(0, sz);
    return str1 == repeat(gcd, str1.length() / sz) &&
           str2 == repeat(gcd, str2.length() / sz);
  }

  string repeat(const string& s, int n) {
    string res;
    for (int i = 0; i < n; ++i)
      res += s;
    return res;
  }
};

class Solution {
  public String gcdOfStrings(String str1, String str2) {
    for (int sz = Math.min(str1.length(), str2.length()); sz > 0; --sz)
      if (isDivisible(str1, str2, sz))
        return str1.substring(0, sz);
    return "";
  }

  // Returns true if str1 and str2 are divisible by str1[0..sz).
  private boolean isDivisible(final String str1, final String str2, int sz) {
    if (str1.length() % sz > 0 || str2.length() % sz > 0)
      return false;
    final String gcd = str1.substring(0, sz);
    return str1.replace(gcd, "").isEmpty() && str2.replace(gcd, "").isEmpty();
  }
}

class Solution:
  def gcdOfStrings(self, str1: str, str2: str) -> str:
    for sz in range(min(len(str1), len(str2)), 0, -1):
      if self._isDivisible(str1, str2, sz):
        return str1[:sz]
    return ''

  def _isDivisible(self, str1: str, str2: str, sz: int) -> bool:
    """Returns True if str1 and str2 are divisible by str1[0..sz)."""
    if len(str1) % sz > 0 or len(str2) % sz > 0:
      return False
    gcd = str1[:sz]
    return str1.replace(gcd, '') == '' and str2.replace(gcd, '') == ''

Approach 2: GCD

• Time: $O(|\texttt{str1}| + |\texttt{str2}|))$
• Space: $O(|\texttt{str1}| + |\texttt{str2}|)$

C++JavaPython

class Solution {
 public:
  string gcdOfStrings(string str1, string str2) {
    if (str1 + str2 != str2 + str1)
      return "";
    const int g = gcd(str1.length(), str2.length());
    return str1.substr(0, g);
  }
};

class Solution {
  public String gcdOfStrings(String str1, String str2) {
    if (!(str1 + str2).equals(str2 + str1))
      return "";
    final int g = gcd(str1.length(), str2.length());
    return str1.substring(0, g);
  }

  private int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
  }
}

class Solution:
  def gcdOfStrings(self, str1: str, str2: str) -> str:
    if str1 + str2 != str2 + str1:
      return ''
    g = math.gcd(len(str1), len(str2))
    return str1[:g]