Задача: 1071. Greatest Common Divisor of Strings
Сложность: easy

Для двух строк s и t мы говорим, что "t делит s", если и только если s = t + t + t + ... + t (т.е. t соединена сама с собой один или более раз).

Даны две строки str1 и str2, верните наибольшую строку x, такую что x делит и str1, и str2.

Пример:

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

👨‍💻 Алгоритм:

1⃣Найдите более короткую строку среди str1 и str2, для простоты пусть это будет str1.

2⃣Начните с base = str1 и проверьте, состоят ли обе строки str1 и str2 из множителей строки base. Если это так, верните base. В противном случае, попробуйте более короткую строку, удалив последний символ из base.

3⃣Если вы проверили все префиксные строки и не нашли строку GCD, верните "".

😎 Решение:

public class Solution {
    public bool Valid(string str1, string str2, int k) {
        int len1 = str1.Length, len2 = str2.Length;
        if (len1 % k > 0 || len2 % k > 0) {
            return false;
        } else {
            string baseStr = str1.Substring(0, k);
            int n1 = len1 / k, n2 = len2 / k;
            return str1 == JoinWords(baseStr, n1) && str2 == JoinWords(baseStr, n2);
        }
    }

    public string JoinWords(string str, int k) {
        var sb = new StringBuilder();
        for (int i = 0; i < k; i++) {
            sb.Append(str);
        }
        return sb.ToString();
    }

    public string GcdOfStrings(string str1, string str2) {
        int len1 = str1.Length, len2 = str2.Length;
        for (int i = Math.Min(len1, len2); i >= 1; i--) {
            if (Valid(str1, str2, i)) {
                return str1.Substring(0, i);
            }
        }
        return "";
    }
}

Ставь 👍 и забирай 📚 Базу знаний