Greatest Common Divisor of Two Strings

easy string math

Problem

Return the longest string that, repeated some number of times, produces both inputs. If a + b ≠ b + a the answer is the empty string. Otherwise the answer is the prefix of length gcd(|a|, |b|).

Inputa = "abcabc", b = "abc"

Output"abc"

"abc" repeated 2× = a, repeated 1× = b. gcd(6, 3) = 3.

from math import gcd
def gcd_of_strings(a, b):
    if a + b != b + a:
        return ""
    return a[: gcd(len(a), len(b))]

function gcdOfStrings(a, b) {
  if (a + b !== b + a) return "";
  const gcd = (x, y) => y === 0 ? x : gcd(y, x % y);
  return a.slice(0, gcd(a.length, b.length));
}

class Solution {
    public String gcdOfStrings(String a, String b) {
        if (!(a + b).equals(b + a)) return "";
        int x = a.length(), y = b.length();
        while (y != 0) { int r = x % y; x = y; y = r; }
        return a.substring(0, x);
    }
}

string gcdOfStrings(string a, string b) {
    if (a + b != b + a) return "";
    int x = a.size(), y = b.size();
    while (y) { int r = x % y; x = y; y = r; }
    return a.substr(0, x);
}

Time: O(|a| + |b|) Space: O(|a| + |b|)