Условие

Даны две строки str1 и str2.

Общий делитель строки — строка, которая может многократно повторяться, чтобы получить str1 и str2.

Верните наибольший общий делитель строк.

Примеры

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

Input: str1 = "ABABAB", str2 = "ABAB” Output: "AB”

Input: str1 = "LEET", str2 = "CODE” Output: "”

Решение

fun gcdOfStrings(str1: String, str2: String): String {
    if (str1 + str2 != str2 + str1) return "" // Проверяем, могут ли строки быть кратными одной подстроке
    fun gcd(a: Int, b: Int): Int = if (b == 0) a else gcd(b, a % b) // НОД длин строк
    return str1.substring(0, gcd(str1.length, str2.length)) // Возвращаем подстроку длины НОД
}

Временная сложность

O(n), где n — длина наибольшей строки.

Пространственная сложность

O(1), так как не используем дополнительную память.