<p>Given a string <code>s</code>, consider all <em>duplicated substrings</em>: (contiguous) substrings of s that occur 2 or more times.&nbsp;The occurrences&nbsp;may overlap.</p>

<p>Return <strong>any</strong> duplicated&nbsp;substring that has the longest possible length.&nbsp;If <code>s</code> does not have a duplicated substring, the answer is <code>&quot;&quot;</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<pre><strong>Input:</strong> s = "banana"
<strong>Output:</strong> "ana"
</pre><p><strong class="example">Example 2:</strong></p>
<pre><strong>Input:</strong> s = "abcd"
<strong>Output:</strong> ""
</pre>
<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>2 &lt;= s.length &lt;= 3 * 10<sup>4</sup></code></li>
	<li><code>s</code> consists of lowercase English letters.</li>
</ul>

"""
How much time have I spent, end-to-end?
    ±1.5 hours
What were the trickiest aspects? Where did you lose the most time?
    The part of pattern search in the string
What are some lessons/insights I gained from this problem?
    The Rabin-Karp algorithm
What would I do differently if I had extra time? What’s remaining to improve?
    I would implement the Rabin-Karp algorithm in my solution
What did I do well?
    I came up with the simple solution leveraging the sliding window algorithm, not the optimal though
Did you use any hints, if yes, what? (please do not give up and look up the hints quickly. if you do need to look up the hints, only use the ones given on the problem page one by one, and DON'T look at youtube videos or full solutions, until you try really hard)
    No
How difficult was the problem (1 super trivial, 10 extremely difficult) (answer this question three times separately for a) implementing quickly b) finding the right approach c) overall)
a) 6
b) 9
c) 8
What's the time & space complexity?
TC: O(n^2)
SC: O(n)
n - number of chars in the string
"""

class Solution:
    def longestDupSubstring(self, s: str) -> str:
        '''
        Solution:
        1. Count every char in the string
        2. When the repeated charecter is appear -> add it to the candidate string
        3. If the candidated is larger then current result -> search the candidate in past substring
        4. Reduce 
        '''
        counter = defaultdict(int)
        result = candidate = ''
        for i, char in enumerate(s):
            counter[char] += 1
            if counter[char] == 1:
                candidate = ''
            elif counter[char] > 1:
                candidate += char
                while len(candidate) > len(result):
                    if s[:i].find(candidate) > -1:
                        result = candidate
                        break
                    else:
                        candidate = candidate[1:]
        return result

17000