Domain 2MediumMEDIUM

Longest Repeating Substring

LeetCode problem 1062: Longest Repeating Substring (medium).

Domain: medium•Updated: 2026-09-08
#String

Problem Breakdown

We need to find the maximum length of a substring that appears at least twice in string S. The occurrences can overlap (e.g., “aaaa” contains two overlapping instances of “aaa”). If no such repeating substring exists, we return 0.

Inputs: A single string S containing lowercase English letters (‘a’-‘z’). Outputs: An integer representing the length of the longest repeating substring.

Implicit Constraints & Edge Cases:

  • Overlap Allowed: As seen in Example 4 (“aaaaa” -> 4), overlapping instances count towards a repeat if they are distinct occurrences (indices differ).
  • No Repeats: If all characters are unique, output is 0.
  • Single Character String: Length 1 cannot have repeats; returns 0.
  • Maximum Constraints: S.length up to 1500 requires an efficient solution (O(N2)O(N^2) or better), as N=1500N=1500 makes naive solutions risky in Python due to overhead, though acceptable for this specific complexity class on LeetCode.

Intuition

A brute-force approach would check every possible substring length and start position against all other substrings using a nested loop structure. This results in roughly O(N3)O(N^3) or worse depending on string comparison implementation, which is too slow given the constraints (1500 characters).

Key Insight: The property of “having a repeating substring” is monotonic with respect to length. If there exists a repeating substring of length L, then there must also exist one of length L-1 (by truncating either end). This allows us to use Binary Search on the Answer. We can search for the maximum valid length in range [0, N].

Optimal Approach:

  1. Binary Search over possible lengths (low, high).
  2. For a given candidate length mid, check if any substring of that length repeats using a Hash Set (or Python’s built-in set).
  3. If valid, try longer lengths; otherwise, try shorter ones.

Approach

  1. Initialize binary search bounds: low = 0 and high = len(S). We want to find the largest mid that satisfies the condition.
  2. While low <= high:
    • Calculate mid = (low + high) // 2.
    • Check Function: Iterate through string S, slicing substrings of length mid. Add each slice to a Set. If we encounter a substring already in the set, it means a repeat exists for this length -> return True.
  3. Update binary search pointers:
    • If check returns True: Store mid as potential answer and try larger lengths (low = mid + 1).
    • Else: Try smaller lengths (high = mid - 1).
  4. Return the stored maximum length (defaulting to 0 if no repeat found).

Complexity Analysis

  • Time: O(N2log⁡N)O(N^2 \log N). The binary search performs log⁡N\log N iterations. Inside each iteration, we iterate through the string of size N and perform slicing/hashing operations proportional to substring length (average case), leading to roughly O(N)O(N) work per check in Python due to slice overhead, but worst-case complexity is bounded by total character processing which sums up quadratically relative to N across iterations. Given N=1500N=1500, this fits well within time limits.
  • Space: O(N2)O(N^2). In the worst case (e.g., “aaaaa…”), we store many substrings in the Set during a check iteration, potentially consuming memory proportional to total characters processed (N×LN \times L).

Solution

class Solution:
    def longestRepeatingSubstring(self, S: str) -> int:
        n = len(S)
        
        # Binary search for the maximum length of repeating substring
        low, high = 0, n
        
        while low <= high:
            mid = (low + high) // 2
            
            if mid == 0: 
                # Length 0 is always possible but we want max > 0 usually.
                # However, logic holds naturally as set check for len=0 returns True immediately?
                # Actually slicing S[i:i] gives empty string "". Empty strings repeat infinitely.
                # We should handle mid=0 explicitly or ensure high starts at n-1 if needed. 
                # But since we want max length > 0, and low starts at 0:
                pass
            
            check = False
            seen = set()
            
            for i in range(n - mid + 1):
                sub = S[i : i + mid]
                
                if sub in seen:
                    return mid # Optimization: If we find a repeat, this length is valid. 
                               # But wait, binary search needs to know *if* it's possible for THIS specific run?
                               # Actually standard BS logic requires returning True/False from check function.
                               # Let's fix the loop structure inside solution below.
                    break
                
                seen.add(sub)
            
            if mid == 0: 
                 low = mid + 1
                 continue
            
            # Re-implementing clean check logic within binary search flow for clarity in final code block

Wait, I need to write the final solution cleanly without debug comments inside. Let’s refine the Python implementation mentally before writing it into the response text.

Refined Code Logic:

  1. low = 0, high = n.
  2. Loop while low <= high:
    • mid = (low + high) // 2
    • If mid == 0: We can treat this as valid but we want to maximize length, so effectively skip or handle naturally? Actually if mid=0 returns True always, binary search will push low up. But wait, Example 1 “abcd” -> Output 0. So answer 0 is possible.
    • Check function: seen = set(), loop i from 0 to n-mid. If slice in seen return True else add.
    • If check returns True (repeat found): store result, try higher (low = mid + 1). Else lower (high = mid - 1).

Wait, Example 4 “aaaaa” -> Output 4. My logic: mid=2 works. ans=2. Try larger. If I use the optimization inside check (returning True immediately), it’s correct for BS state? Yes, if any repeat exists at length L, then valid is true.

Final Code Structure:

class Solution:
    def longestRepeatingSubstring(self, S: str) -> int:
        n = len(S)
        
        # Binary search range for the answer (length of substring)
        left, right = 0, n
        
        while left <= right:
            mid = (left + right) // 2
            
            if mid == 0: 
                # Length 0 is trivially repeating but we want max length.
                # If low=0 and high=n, mid can be 0 initially? No, usually n>=1 so mid >= 0.
                # We need to handle the case where no repeat exists (return 0).
                pass
            
            seen = set()
            found_repeat = False
            
            for i in range(n - mid + 1):
                sub = S[i : i + mid]
                
                if sub in seen:
                    found_repeat = True
                    break
                
                seen.add(sub)
            
            # If we find a repeat of length 'mid', try longer lengths. 
            # We store the result and move left up to search for larger valid lengths.
            if found_repeat or mid == 0:
                ans = max(ans, mid) # Actually simpler logic in BS usually updates low/high directly?
                # Standard pattern: If possible (found), try higher range [mid+1, right]
                # But we need to track the answer separately because binary search on boolean property 
                # finds boundary. Let's use standard 'if found' -> ans = mid; left = mid + 1 logic?
                # Wait, if I find a repeat at `mid`, then any length < `mid` also works (monotonicity).
                # So we want to push up. 
                pass
            
            # Let's write the clean version in the final block carefully.

Correct BS Logic for Max Value: If check(mid) is True: We know a solution exists at length mid. Since monotonic, larger lengths might also exist. Store ans = mid and try higher (left = mid + 1). Else (check fails): Length mid too big. Try smaller (right = mid - 1).

Wait, Example “abcd” -> Output 0. My code: check(2) False, right=1… eventually returns ans initialized to 0? Yes. Example “aaaaa”: check(4) True (indices 0..3 and 1..4). ans becomes 4. Check(5) False. Returns 4.

Wait, one optimization: If I find a repeat, do I need to continue checking the rest of the string for that specific length? No, if any pair repeats, it’s valid. But wait, Example “aabcaabdaab” -> Output 3 (“aab”). If mid=2 (“aa”, “a…”, etc). If we find one repeat, is it guaranteed to be true? Yes. However, does finding a repeat mean all substrings of length mid are not needed? No, just existence matters for the boolean check in BS.

Wait, there’s a small catch with mid=0. If I initialize ans = 0, and loop runs: left=0, right=n. mid can be large or small. If n=1500, mid starts at ~750. Eventually it narrows down to where check fails for high lengths but succeeds for low ones (or none). If no repeat exists ever, loop finishes and returns 0? Yes if I initialize result variable correctly.

Let’s write the code block now ensuring clean Python syntax.

class Solution:
    def longestRepeatingSubstring(self, S: str) -> int:
        n = len(S)
        
        # Binary search for length L in range [0, n]
        left, right = 1, n - 1 
        ans = 0
        
        while left <= right:
            mid = (left + right) // 2
            
            if mid == 0:
                break
                
            seen = set()
            found = False
            for i in range(n - mid + 1):
                sub = S[i : i+mid]
                if sub in seen:
                    found = True
                    break
                seen.add(sub)
            
            if found:
                ans = mid
                left = mid + 1 # Try longer length
            else:
                right = mid - 1 # Length too big
        
        return ans

Wait, left starts at 0 or 1? If I start at 0 and check(0), it’s always true (empty string repeats). But we want max non-zero. Example “abcd” -> output 0. My code with range [1, n-1] handles this: if no repeat found in any length >= 1, ans remains 0. Wait, what about input length 1? S=“a”. Range [1, 0]. Loop doesn’t run. Returns 0. Correct. Input “aa”. N=2. Range [1, 1]. Mid=1. Check len 1 (“a”, “a”). Found=True. Ans=1. Left=2. Loop ends. Return 1? Wait Example says “aaaa” -> output 4 (len 5). Wait, for S=“aa”. Longest repeating is “a”? Yes length 1. Example 3: “aabcaabdaab”, Output 3 (“aab”). My code should find this.

One detail on constraints: S.length >= 1. If I set range [0, n], and handle mid=0 case? Usually simpler to init ans = 0. Range left = 0, right = len(S) - 1 (since max repeating length is N-1). Or just len(S) if we want to be safe. If I use range [0, n]: Mid can be (n)/2. If check(n/2) fails… eventually checks small lengths. Actually, for “abcd”, len 4. Range [0, 3]. Max possible repeating is < N? Yes because need two occurrences (indices i and j where |i-j| >= mid). So max length <= N-1. So right = n - 1 is safer optimization but [n] works too with check logic handling it naturally (check(n) will fail for any string unless empty, wait “aaaaa” len 5 -> repeat of len 4 exists. Repeat of len 5 does not exist). So max possible answer is N-1? Wait Example 4: S=“aaaaa”, Output 4. Length 5 repeats? No (only one instance at index 0..4). So right = n - 1 is correct upper bound for valid repeating substring length. However, if I set right = len(S), check(len=S) will always fail unless string empty? Wait “aaaaa” -> S[0:5] exists once. Set adds it. Loop finishes. Found=False. Correct. So range [1, n-1] is sufficient for non-zero answers. But to be robust against N=1 (returns 0), I should handle ans = 0. I will use left = 0, right = len(S) and just ignore mid==0 or treat it as valid but not updating ans? Actually, if mid becomes 0 in BS loop with range [0, n]: check(0) is always True (empty string repeats). Then we set ans=0. But wait, Example “abcd” -> Output 0. If I find repeat at len 0, do I return 0? Yes. But if I have a valid answer > 0 later in BS, it will overwrite ans. Wait, monotonicity: If length L works, does length L-1 work? Yes. So finding “abcd” -> check(2) False… eventually check(0) True. ans would be updated to 0 at the end if I don’t handle carefully. Actually standard pattern for Max Value BS is: If valid(mid): ans = mid; low = mid + 1 (We found a solution, try bigger). Else: high = mid - 1 (Too big).

So even if check(0) returns True, ans becomes 0. If no larger works, we return 0. This is correct for “abcd”. However, to avoid infinite loops or confusion with empty strings in set logic, I will start search from length 1? No, because answer can be 0. I’ll stick to range [0, n] but handle mid=0 gracefully (it’s always valid). But wait, if check(0) is True, we try higher lengths. If all fail up to N-1, ans remains whatever last successful was? Wait, if I start with low=0, high=n. Mid ~ n/2. Fails. High drops. Eventually mid becomes 0 or small. If “abcd”: check(3) False… check(1) False (a,b,c,d unique). check(0) True. Ans updates to 0? Wait, if ans is initialized to -1 or something? No, init to 0. If I find valid at mid=2 for some string, ans becomes 2. Then try higher… fail… eventually hit low where it works (smaller). Actually, the logic should be: We want MAX length. If check(mid) is True -> ans = mid, low = mid + 1. Else -> high = mid - 1.

For “abcd”: Range [0, 4]. Mid=2. Check(2): False (“ab” vs “cd”, etc). High=1. Mid=(0+1)//2 = 0. Check(0): True (empty string repeats? Or just skip?). If I treat check(0) as valid: Ans=0, Low=1. Loop ends. Return 0. Correct.

Wait, if “aaaaa”: Range [0, 5]. Mid=2 -> Valid. Ans=2, Low=3. Mid=(3+5)//2 = 4. Check(4) True (“aaaa” repeats). Ans=4, Low=5. Mid=(5+5)//2 = 5. Check(5) False (only one “aaaaa”). High=4. Loop ends. Return 4. Correct.

So left can be initialized to 0? Yes. But slicing with length 0 is