LeetCode 1062. Longest Repeating Substring

Показать описание

Рекомендации по теме

Комментарии

I really loved the Rabinkarp implementation. I struggled to make sense of Rabinkarp before watching this video. This really helped. Thank you for an excellent video

PEqualsN.P

Great Explanation. Keep it up. Thank you

shubhamkiingale

isnt mid = left + (right - left) = right?
mid = right??

natisaver

Can you post the code as well. Otherwise good video. Also don't you need to use modulus?

senthilvaithi

Hey Chang, a very good video. 42 minutes is worth it. Before this video, I was thinking of suggesting you to try to have the video under 15 minutes. (I usually watch all the video with 1.25 speed. I need to cover more stuff with the little time and attention span that I have.) More than 15 minutes tires me out since I need to code this one after watching it and need to study the another one (if the video is longer, I cannot study another problem because it has used up the time and energy). Of course, there will be exception like this video which cover three solution with progression. Well, these are my own experience and you can do what you like as a creator.

aunnfriends

class Solution(object):

# Method 4 Using binary search by a particular substring length AND USING ROLLING HASH TO OPTIMIZE THE SLICING PART IN FINDING THE SUBSTR
# TC :
# SC :

def helper(self, mid, n, s, nums):
seen = set()
'''
for i in range(n-mid+1):
substr = s[i:i+mid]
hash_val = hash(substr)
if hash_val in seen:
return True
else:
seen.add(hash_val)
return False'''

h = 0

# starting hashing
for i in range(mid):
h = h*26 + nums[i]

seen.add(h)

for i in range(1, n-mid+1):
h = h * 26 - nums[i-1] * 26**mid + nums[i+mid-1] *26**0
if h in seen :
return True
return False

def longestRepeatingSubstring(self, s):
"""
:type s: str
:rtype: int
"""
n = len(s)

nums = [ord(ch) - ord('a') for ch in s]

left = 0
right = n-1

while left <= right:
mid = left + (right-left) // 2
if self.helper(mid, n, s, nums) == True:
left = mid + 1
else:
right = mid - 1

return left - 1

Not sure why this is not working for one of the test cases
Can someone help me out?

muktaparab

Great Explanation. Keep it up. Thank you

parasnath

LeetCode 1062. Longest Repeating Substring

LeetCode 1062. Longest Repeating Substring

Longest Repeating Substring | LeetCode 1062 | Facebook Interview Question

1062. Longest Repeating Substring (Leetcode Medium)

1062 Longest Repeating Substring

1062. Longest Repeating Substring - Week 1/5 Leetcode August Challenge

3 approaches to LeetCode 1062 Longest Repeating Substring | JSer - JavaScript & Algorithm

Longest Repeating Substring

Longest Repeating Character Replacement - Leetcode 424 - Python

Leetcode - Longest Duplicate Substring (Python)

LeetCode Explained - Longest Substring w/ UNIQUE Characters [EASIEST SOLUTION]

Leetcode solving: 1668. Maximum Repeating Substring

Longest Repeated Substring suffix array

[C++] [EN] Leetcode 1062

Longest Non-Overlapping Repeating Substring - Amazon Coding Interview Question | Dynamic Programming

Longest Repeating SubString || Problem of the day || Medium Problem || Coding Ninja || 17 Sep 2023

LeetCode 459 - Repeated Substring Pattern (full version on tiktok)

Coding Challenge #2 - HOW TO find the LONGEST substring \W repeating chars (+ UnitTests)? | 4K

longest duplicate substring leetcode | Rabin–Karp algorithm | java solution

1668. Maximum Repeating Substring (Leetcode Easy)

Leetcode Longest Duplicate Substring Java Solution

Longest Duplicate Substring | Day 19 | [June LeetCoding Challenge] [Leetcode #1044] [2020]

【Leetcode II 2/50】459. Repeated Substring Pattern (~Easy) Got LeetCode Daily Coin =))

Longest Substring Without Repeating Characters | Leet code 3 | Theory explained + Python code

Longest Repeating Subsequence | Dynamic Programming | LCS