180-strings-problem-18.md

Strings Problem 18

LeetCode: https://leetcode.com/problems/repeated-substring-pattern/ Difficulty: Medium

Problem

Solve this strings problem efficiently.

Brute Force Approach

function solve(s) {
    let maxLength = 0;
    // Check all substrings
    for (let i = 0; i < s.length; i++) {
        for (let j = i; j < s.length; j++) {
            const substring = s.slice(i, j + 1);
            if (isValid(substring)) {
                maxLength = Math.max(maxLength, substring.length);
            }
        }
    }
    return maxLength;
}

⏱️ Time: O(n²) or O(n³)
💾 Space: O(n)

Optimal Approach

function solve(s) {
    const set = new Set();
    let left = 0, right = 0, maxLength = 0;
    
    // Sliding window approach
    while (right < s.length) {
        if (!set.has(s[right])) {
            set.add(s[right]);
            maxLength = Math.max(maxLength, right - left + 1);
            right++;
        } else {
            set.delete(s[left]);
            left++;
        }
    }
    return maxLength;
}

⏱️ Time: O(n) or O(n log n)
💾 Space: O(n) or O(1)

Visual Diagram

String: "abcdef"
Window: [abc]def
         ↑ ↑
         L R

Sliding Window moves right:
a[bcde]f
  ↑   ↑
  L   R

---

Visit LeetCode for full problem description.