<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>

/***********************************************************************

string_view is just like a view of a string. We can a have a view over a string and can make
substrings from the same string_view. Unlike the strings, string_view does not creates another
string. It can rather be viewed as a structure which keeps a record of the initial pointer and
the length of the underlying string.

https://www.learncpp.com/cpp-tutorial/introduction-to-stdstring_view/

*************************************************************************/

class Solution {
public:
    string longestDupSubstring(string str) {

        unordered_set<string_view> hash;

        string_view finalstr;
     
        int start = 0;
        int end = str.size() - 1;
     
        while(start <= end) {
            int len = (start + end) / 2;
            bool found = false;

// cout << " Size : "  <<  str.size()  <<  "  start :  " << start <<  "  end :  " << end ;
// cout << "  len : "  << len   <<  "  TT:  "  << (str.size() - len + 1)  << endl;

            for (int i = 0; i < str.size() - len + 1; i++) {
                string_view sv = string_view(str).substr(i, len);
                
// cout << "String str  : " << str.substr(i, len) << endl;;

                if (hash.find(sv) != hash.end()) 
                {
                    found = true;
                    finalstr = sv;
                    break;
                } 
                else 
                {
                    hash.emplace(sv);
                }
            }

            if (found) 
            {
               start = len + 1;
            } 
            else 
            {
               end = len - 1;
            }
          
            hash.clear();
        }
     
        return {finalstr.begin(), finalstr.end()};
    }
};
129380