Teaching Kids Programming – Greatest Common Divisor of Strings

Teaching Kids Programming: Videos on Data Structures and Algorithms

For two strings s and t, we say “t divides s” if and only if s = t + … + t (t concatenated with itself 1 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: “”

Example 4:
Input: str1 = “ABCDEF”, str2 = “ABC”
Output: “”

str1 and str2 consist of English uppercase letters.

The greatest common divisor must be a prefix of each string, so we can try all prefixes.

GCD of String via Checking the Largest Prefix

We can check the largest prefix string that can form both string. The time complexity is O(N^2).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution:
    def gcdOfStrings(self, str1: str, str2: str) -> str:
        n1 = len(str1)
        n2 = len(str2)
        
        def check(s, prefix):
            ls = len(s)
            lp = len(prefix)
            if ls % lp != 0:
                return False
            return prefix * (ls // lp) == s
        
        for i in range(min(n1, n2), 0, -1):
            prefix = str1[:i]
            if check(str1, prefix) and check(str2, prefix):
                return prefix
        return ""

class Solution:
    def gcdOfStrings(self, str1: str, str2: str) -> str:
        n1 = len(str1)
        n2 = len(str2)
        
        def check(s, prefix):
            ls = len(s)
            lp = len(prefix)
            if ls % lp != 0:
                return False
            return prefix * (ls // lp) == s
        
        for i in range(min(n1, n2), 0, -1):
            prefix = str1[:i]
            if check(str1, prefix) and check(str2, prefix):
                return prefix
        return ""

Algorithm to Check GCD of Two Strings

If two strings have a non-empty GCD string/prefix, it must satisfy that A+B is B+A. After passing the test, we then use the GCD function to get the length of the prefix.

1
2
3
4
5
6

class Solution:
    def gcdOfStrings(self, str1: str, str2: str) -> str:
        if str1 + str2 != str2 + str1:
            return ""
        k = gcd(len(str1), len(str2))
        return str1[:k]

class Solution:
    def gcdOfStrings(self, str1: str, str2: str) -> str:
        if str1 + str2 != str2 + str1:
            return ""
        k = gcd(len(str1), len(str2))
        return str1[:k]

The time complexity is O(N+M) where N and M are the length of two strings respectively.

See also: How to Compute the Greatest Common Divisor of Strings

–EOF (The Ultimate Computing & Technology Blog) —