Longest Repeating Substring - Practice Coding Problems

Longest Repeating Substring - Problem

String Binary Search Dynamic Programming Rolling Hash Suffix Array Hash Function Medium

Given a string s, return the length of the longest repeating substring. If no repeating substring exists, return 0.

A repeating substring is a substring that occurs at least twice in the string.

Input & Output

Example 1 — Basic Repeating Pattern

$ Input: s = "abcabc"

› Output: 3

💡 Note: The substring "abc" appears twice: at positions 0-2 and 3-5, so the longest repeating substring has length 3

Example 2 — Single Character Repetition

$ Input: s = "aabaaaba"

› Output: 2

💡 Note: The substring "aa" appears multiple times, and "aaba" appears twice, but "aa" has length 2 which is the maximum

Example 3 — No Repetition

$ Input: s = "abcdef"

› Output: 0

💡 Note: No substring appears more than once, so return 0

Constraints

1 ≤ s.length ≤ 1000
s consists of lowercase English letters

Visualization

Tap to expand

Understanding the Visualization

Input

String with potential repeating patterns

Process

Find all substrings that appear multiple times

Output

Length of the longest repeating substring

Key Takeaway

🎯 Key Insight: Compare the string with shifted versions of itself to efficiently find the longest pattern that repeats

Asked in

G Google 25 a Amazon 20 M Microsoft 15 f Facebook 12

The key insight is to compare the string with shifted versions of itself to find repeating patterns. The optimal approach uses binary search on the answer combined with rolling hash for efficient duplicate detection. Time: O(n log n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force	O(n³)	O(n²)	Check all possible substrings for duplicates
Binary Search + Rolling Hash	O(n log n)	O(n)	Binary search on answer length with hash-based duplicate detection
Dynamic Programming	O(n²)	O(n²)	Compare string with itself using 2D DP table

Brute Force — Algorithm Steps

Generate all possible substrings
For each substring, count occurrences
Track maximum length of duplicated substrings

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate

Create all possible substrings

Count occurrences of each substring

Track

Keep maximum length of repeated substrings

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(char* s) {
    int n = strlen(s);
    int maxLen = 0;
    
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j <= n; j++) {
            int len = j - i;
            int count = 0;
            for (int k = 0; k <= n - len; k++) {
                if (strncmp(s + i, s + k, len) == 0) {
                    count++;
                    if (count >= 2) {
                        if (len > maxLen) {
                            maxLen = len;
                        }
                        break;
                    }
                }
            }
        }
    }
    
    return maxLen;
}

int main() {
    char s[1001];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    
    int result = solution(s);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

O(n²) substrings × O(n) to check each occurrence

⚠ Quadratic Growth

Space Complexity

O(n²)

Hash set stores up to O(n²) substrings

⚠ Quadratic Space

35.0K Views

Medium Frequency

~25 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler