LeetCode //C - 1071. Greatest Common Divisor of Strings

1071. Greatest Common Divisor of Strings

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: “”

Constraints:

• 1 <= str1.length, str2.length <= 1000
• str1 and str2 consist of English uppercase letters.

From: LeetCode
Link: 1071. Greatest Common Divisor of Strings

---

Solution:

Ideas：

1. Check Concatenation Equality: Concatenate str1 with str2 and str2 with str1. If these concatenated strings are not equal, there is no common divisor string and we should return an empty string.

2. Find the GCD of the Lengths: If the strings pass the first check, find the GCD of the lengths of the two strings.

3. Create and Return the GCD String: The GCD string is a substring of either string with length equal to the GCD of the lengths of the two strings.

Code:

// Function to find the greatest common divisor of two integers
int gcd(int a, int b) {
    while (b != 0) {
        int t = b;
        b = a % b;
        a = t;
    }
    return a;
}

// Function to find the greatest common divisor of two strings
char* gcdOfStrings(char* str1, char* str2) {
    int len1 = strlen(str1), len2 = strlen(str2);

    // Allocate memory for concatenated strings
    char *concat1 = (char *)malloc(sizeof(char) * (len1 + len2 + 1));
    char *concat2 = (char *)malloc(sizeof(char) * (len1 + len2 + 1));

    // Concatenate str1 and str2
    strcpy(concat1, str1);
    strcat(concat1, str2);

    // Concatenate str2 and str1
    strcpy(concat2, str2);
    strcat(concat2, str1);

    // Check if concatenated strings are equal
    if (strcmp(concat1, concat2) != 0) {
        free(concat1);
        free(concat2);
        return "";
    }

    free(concat1);
    free(concat2);

    int gcdLength = gcd(len1, len2);

    char *result = (char *)malloc(sizeof(char) * (gcdLength + 1));
    strncpy(result, str1, gcdLength);
    result[gcdLength] = '\0';

    return result;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44