1062. Longest Repeating Substring
Problem Description
The problem asks for the length of the longest repeating substring within a given string s
. A repeating substring is defined as a sequence of characters that appears more than once in the original string. To clarify, if the string was "abab", the longest repeating substring would be "ab", which has a length of 2. If no such repeating substring exists, such as in a string with all unique characters like "abc", the function should return 0.
Intuition
The solution to this problem involves dynamic programming, a method for solving complex problems by breaking them down into simpler subproblems. The intuition behind using dynamic programming for this problem is the idea of comparing characters at different positions and building a table that records the lengths of repeating substrings ended at those positions.
This is accomplished by initializing a square matrix dp
with the dimensions of the string's length, where dp[i][j]
will be used to store the length of the longest repeating substring that ends with the characters s[i]
and s[j]
. We can then iterate over each position i in the string, and for each i, iterate again through each position j from i+1 to the end of the string. If the characters at positions i and j are the same, it means there's a repeating character, and we can build upon the length of previously found repeating substrings.
Specifically, if s[i]
equals s[j]
, then dp[i][j]
is the length of the repeating substring that ended just before i and j (which is dp[i - 1][j - 1]
), plus 1 for the current matching characters. If i is 0, there's no previous character, so dp[i][j]
is just set to 1. Along the way, we keep track of the maximum length found in variable ans
.
Every time we find a matching pair of characters, we update ans
to hold the maximum length of any repeating substring found so far. Through this process, we arrive at the longest repeating substring's length without having to check each possible substring individually.
Learn more about Binary Search and Dynamic Programming patterns.
Solution Approach
The implementation of the solution uses dynamic programming, explicitly utilizing a 2D array (referred to as a matrix) for storing the lengths of repeating substrings. Here's how the code works:
-
Initialize a 2D list (matrix)
dp
, where each elementdp[i][j]
represents the length of the longest repeating substring that ends withs[i]
ands[j]
. Set the entire matrix to 0 initially because we haven't found any repeating substrings yet. -
Set a variable
ans
to 0. This variable will keep track of the length of the longest repeating substring found so far. -
Iterate over each character in the string using two nested loops:
a. The outer loop goes through each character in the string with index
i
.b. The inner loop starts from
i+1
and goes to the end of the string with indexj
.c. For each pair of indices
i
andj
, check ifs[i]
is equal tos[j]
. If they are:1 i. If `i` is greater than 0, update `dp[i][j]` to be `dp[i - 1][j - 1] + 1`. This is because a matching pair of characters extends the length of the repeating substring by 1 compared to the substring that ended just before these indices. 2 3 ii. If `i` is equal to 0, set `dp[i][j]` to 1 since there are no previous characters to consider, and thus we have found a repeating substring of length 1.
d. Update the
ans
variable with the larger of its current value ordp[i][j]
, ensuringans
always holds the length of the longest repeating substring found. -
After completing the iterations, return the value stored in
ans
, which now represents the length of the longest repeating substring ins
.
The algorithm uses a dynamic programming matrix to avoid redundant work, building up the solution based on previously computed values. By checking only pairs of indices where j
is greater than i
, the algorithm ensures that only substrings are considered, not individual characters or the entire string. This approach efficiently solves the problem with O(n^2)
time complexity and O(n^2)
space complexity, where n
is the length of the string s
.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's take a small example string s = "aabba"
. According to the given solution approach, we want to find the length of the longest repeating substring in s
. Here is how the approach works step-by-step:
-
We initialize a matrix
dp
of 5x5 dimensions (since the strings
has a length of 5) with all values set to 0. The matrix looks like this:1dp = [ 2 [0, 0, 0, 0, 0], 3 [0, 0, 0, 0, 0], 4 [0, 0, 0, 0, 0], 5 [0, 0, 0, 0, 0], 6 [0, 0, 0, 0, 0] 7]
-
We set
ans
to 0. -
We start iterating over each character in
s
using two nested loops:-
Outer loop with index
i
from 0 to 4. -
Inner loop with index
j
fromi+1
to 4.
-
-
Now we work through the loops:
-
On the first iteration (
i=0, j=1
), we find thats[0]
(which is 'a') is equal tos[1]
(also 'a'). Sincei
is 0, we setdp[0][1]
to 1.ans
is updated to 1.1dp = [ 2 [0, 1, 0, 0, 0], 3 [0, 0, 0, 0, 0], 4 ... 5]
-
On iteration (
i=1, j=2
),s[1]
is 'a' buts[2]
is 'b', so we do nothing as they don't match. -
On iteration (
i=3, j=4
), we find a match as boths[3]
ands[4]
are 'a'. Sincei > 0
, we setdp[3][4]
todp[2][3] + 1
which is 1 (since 'b'[3] and 'b'[4] don't match,dp[2][3]
is 0). Now,ans
is updated to 1.1dp = [ 2 ... 3 [0, 0, 0, 0, 1] 4]
-
-
None of the remaining iterations of the loops yield any greater repeating substring, so
ans
remains 1. -
After iterating through the string and updating the
dp
matrix, we find that the value ofans
remains 1.
Thus, the length of the longest repeating substring in the example string "aabba" is 1, and that repeating substring is "a".
Solution Implementation
1class Solution:
2 def longestRepeatingSubstring(self, s: str) -> int:
3 # Length of the input string
4 n = len(s)
5
6 # Initialize a 2D array(dynamically programming table)
7 # to store lengths of repeating substrings
8 dp_table = [[0] * n for _ in range(n)]
9
10 # Variable to store the length of the largest repeating substring
11 max_length = 0
12
13 # Iterate through each character in the string
14 for i in range(n):
15 # Compare with other characters in the string to the right
16 for j in range(i + 1, n):
17 # Check if the characters s[i] and s[j] match
18 if s[i] == s[j]:
19 # Extend the length of the repeating substring
20 # If i is not 0, get the previous length from the dp table, else just start with length 1.
21 dp_table[i][j] = dp_table[i - 1][j - 1] + 1 if i else 1
22 # Update the max_length if the current repeating substring is longer
23 max_length = max(max_length, dp_table[i][j])
24
25 # Return the length of the longest repeating substring
26 return max_length
27
1class Solution {
2 public int longestRepeatingSubstring(String s) {
3 int length = s.length(); // Length of the string 's'
4 int longestLength = 0; // Variable to store the length of the longest repeating substring
5 int[][] dp = new int[length][length]; // dp[i][j] will hold the length of the longest repeating substring ending at i and j
6
7 // Iterate through the string 's'
8 for (int i = 0; i < length; ++i) {
9 for (int j = i + 1; j < length; ++j) {
10 // Check if characters at positions i and j are the same.
11 if (s.charAt(i) == s.charAt(j)) {
12 // If they match and are not at the first character,
13 // increment the length of the repeating substring by 1.
14 // Otherwise, set the repeating substring length to 1 as it's the start of a possible repeating pattern.
15 dp[i][j] = i > 0 ? dp[i - 1][j - 1] + 1 : 1;
16 // Update the longestLength if the current repeating substring is the longest found so far.
17 longestLength = Math.max(longestLength, dp[i][j]);
18 }
19 // If they don't match, the default value of dp[i][j] remains 0, indicating no repetition.
20 }
21 }
22 return longestLength; // Return the length of the longest repeating substring.
23 }
24}
25
1class Solution {
2public:
3 int longestRepeatingSubstring(string s) {
4 int length = s.size(); // Get the size of the string
5 // Create a 2D DP table with 'length' rows and 'length' columns initialized to 0
6 vector<vector<int>> dp(length, vector<int>(length, 0));
7 int longest = 0; // Variable to store the length of the longest repeating substring
8
9 // Iterate over the string with two pointers
10 for (int i = 0; i < length; ++i) {
11 for (int j = i + 1; j < length; ++j) {
12 // If characters at the current position in both pointers match
13 if (s[i] == s[j]) {
14 // Check if it is not the first character, then add 1 to the length of substring
15 // found till the previous characters else start with 1
16 dp[i][j] = (i > 0) ? dp[i - 1][j - 1] + 1 : 1;
17 // Update the longest substring found so far
18 longest = max(longest, dp[i][j]);
19 }
20 // If characters don't match, dp[i][j] remains 0 as initialized
21 }
22 }
23 // Return the length of longest repeating substring
24 return longest;
25 }
26};
27
1function longestRepeatingSubstring(s: string): number {
2 const length = s.length; // Get the length of the string
3 // Create a 2D DP array with 'length' rows and 'length' columns initialized to 0
4 const dp: number[][] = Array.from({ length }, () => Array(length).fill(0));
5 let longest = 0; // Variable to store the length of the longest repeating substring
6
7 // Iterate over the string with two pointers
8 for (let i = 0; i < length; ++i) {
9 for (let j = i + 1; j < length; ++j) {
10 // If characters at the current position in both pointers match
11 if (s[i] === s[j]) {
12 // Check if it is not the first character, then add 1 to the length of the substring
13 // found till the previous characters; otherwise, start with 1
14 dp[i][j] = (i > 0) ? dp[i - 1][j - 1] + 1 : 1;
15 // Update the longest substring found so far
16 longest = Math.max(longest, dp[i][j]);
17 }
18 // If characters don't match, dp[i][j] remains 0 as initialized
19 }
20 }
21 // Return the length of the longest repeating substring
22 return longest;
23}
24
Time and Space Complexity
Time Complexity
The provided code uses a double for-loop to iterate over all possible starting positions of substrings in the string s
, which has the length n
. Inside these loops, it checks if two characters in s
are equal and if so, updates the dynamic programming (DP) table.
The outer loop runs n
times, and the inner loop can run up to n
times as well, which could suggest an O(n^2)
complexity. However, since the inner loop starts at i + 1
, the number of iterations in the inner loop decreases as i
increases. The total number of iterations could then be roughly calculated as the sum of the first n
natural numbers, minus the diagonal elements (which are not accessed), which is (n * (n - 1)) / 2
, which is still in the order of O(n^2)
.
Therefore, the time complexity of the code is O(n^2)
.
Space Complexity
The space complexity is dominated by the space used to store the dynamic programming (DP) table called dp
, which is a 2D array of size n x n
. Since the DP table is filled with 0 values at the beginning, and no other data structures scale with the size of n
grow, the space complexity is O(n^2)
.
Learn more about how to find time and space complexity quickly using problem constraints.
Is the following code DFS or BFS?
1void search(Node root) { 2 if (!root) return; 3 visit(root); 4 root.visited = true; 5 for (Node node in root.adjacent) { 6 if (!node.visited) { 7 search(node); 8 } 9 } 10}
Recommended Readings
Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.