_1062. Longest Repeating Substring.md

1062. Longest Repeating Substring

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : August 01, 2024

Last updated : August 01, 2024

---

Related Topics : String, Binary Search, Dynamic Programming, Rolling Hash, Suffix Array, Hash Function

Acceptance Rate : 62.58 %

---

Version 1: Semi Brute Force

This version simply iterated with a set to see if the case was found before. If it was, change the longest recorded case.

Optimizations:

• j from i + 1 + longest to end $\rightarrow$ since shorter strings are redundant
• substr set --> to avoid having to double the iterations

This ends up being $O(n^3)$ due to the $O(n^2)$ looping and $O(n)$ substring pulling / hash making.

---

Solutions

• m1062 v1 Mostly Brute Force.py

Python

m1062 v1 Mostly Brute Force.py

class Solution:
    def longestRepeatingSubstring(self, s: str) -> int:
        longest = 0
        substr = set()
        for i in range(len(s)) :
            for j in range(i + 1 + longest, len(s) + 1) :
                if s[i:j] in substr :
                    longest = j - i
                else :
                    substr.add(s[i:j])

        return longest