Repeated Substring Pattern

https://leetcode.com/problems/repeated-substring-patternEasy

Условие

Дана строка s. Нужно определить, можно ли ее сформировать путем повторения подстроки более одного раза. Вернуть true, если такая подстрока существует, иначе вернуть false.

Примеры

Input: s = “abab”

Output: true

Explanation: Строку можно построить как “ab” + “ab”.
Input: s = “aba”

Output: false
Input: s = “abcabcabcabc”

Output: true

Explanation: Строку можно построить как “abc” + “abc” + “abc” + “abc”.

Решение

fun repeatedSubstringPattern(s: String): Boolean {
    val n = s.length

    // Проходим по всем возможным длинам подстроки от 1 до n/2
    for (len in 1..n / 2) {
        if (n % len == 0) {  // Подстрока может быть повторена, только если длина делится на len без остатка
            var match = true
            for (i in len until n) {
                if (s[i] != s[i % len]) {  // Проверяем, совпадают ли символы
                    match = false
                    break
                }
            }
            if (match) return true  // Если нашли повторяющийся шаблон, возвращаем true
        }
    }
    return false  // Если не нашли подходящий шаблон, возвращаем false
}

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

O(n²), где n — длина строки s, так как для каждой возможной длины подстроки мы проверяем всю строку на повторение.

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

O(1), так как не используется дополнительная память, зависящая от размера входных данных.