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

/*
Just do a rolling hash - so we fix the longest subarray that we will 
consider perhaps? Binary search on the answer? 

Let f(n) := a boolean value indicating if we have duplicate substrings of
length n. 

How do we compute this? Keep a rolling hash. How do we do this? 

(a1 * 100) + (a2 * 10) + (a3 * 1)

To remove an item -> 
*/

using HashT = long long;

template<long Mod, long Base = 26>
class ModdedStringHash {
private:
    std::reference_wrapper<const string> sRef;
    size_t lPtr = 0;
    size_t rPtr = 0;
    std::vector<long> powers;

    static int charVal(char c)
    {
        return c - 'a';
    }

    HashT m_hashCode = 0;
public:
    ModdedStringHash(const string& s) : sRef(s)
    {
        powers = std::vector<long>(s.size());
        powers.front() = 1;
        for(auto it = ++powers.begin(); it != powers.end(); ++it)
        {
            auto before = it;
            --before;
            *it = (*before * Base) % Mod;
        }
    }
    void popLeft()
    {
        const string& s = sRef;
        if(lPtr == rPtr || lPtr == s.size())
        {
            throw std::runtime_error{"popBack from empty hash"};
        }
        // e.x. lPtr = 0, rPtr = 1 => 
        //  hash = 1 * charVal(s[0]), rPtr - lPtr - 1 = 0
        m_hashCode += Mod;
        m_hashCode -= (charVal(s[lPtr]) * powers[rPtr - lPtr - 1]) % Mod;
        m_hashCode = (m_hashCode + Mod) % Mod;
        lPtr++;
    }
    void pushRight()
    {
        const string& s = sRef;
        if(rPtr == s.size())
        {
            throw std::runtime_error{"pushRight to full hash"};
        }
        m_hashCode = (m_hashCode*Base + charVal(s[rPtr++])) % Mod;
    }
    HashT hashCode() const
    {
        return m_hashCode % Mod;
    }
};

class StringHash
{
private:
    ModdedStringHash<100003679> hash1;
    ModdedStringHash<500000227> hash2;
public:
    StringHash(const std::string& s)
        : hash1(s), hash2(s)
    {}
    void pushRight()
    {
        hash1.pushRight();
        hash2.pushRight();
    }
    void popLeft()
    {
        hash1.popLeft();
        hash2.popLeft();
    }
    HashT hashCode() const
    {
        return hash1.hashCode() * hash2.hashCode();
    }
};

class Solution {
private:

    bool dupSubstringExists(const string& s, size_t targetLen)
    {     
        if(targetLen == 0)
        {
            return true;
        }
        if(targetLen > s.size())
        {
            return false;
        }

        StringHash hasher{s};
        for(size_t i = 0; i < targetLen; ++i)
        {
            hasher.pushRight();
        }

        std::unordered_set<HashT> seenHashes = {hasher.hashCode()};

        for(size_t i = 1; i + targetLen <= s.size(); ++i)
        {
            hasher.pushRight();
            hasher.popLeft();

            HashT newCode = hasher.hashCode();

            if(seenHashes.count(newCode) > 0)
            {
                return true;
            }
            seenHashes.insert(newCode);
        }
        return false;
    }
    /*
        If a duplicate substring of length targetLen exists in s, 
        retrieve it and return it
    */
    std::optional<string> getDupSubstring(const string& s, size_t targetLen)
    {
        if(targetLen == 0)
        {
            return "";
        }
        StringHash hasher{s};

        for(size_t i = 0; i < targetLen; ++i)
        {
            hasher.pushRight();
        }

        std::unordered_set<HashT> seenHashes = {hasher.hashCode()};

        for(size_t i = 1; i + targetLen <= s.size(); ++i)
        {
            hasher.pushRight();
            hasher.popLeft();
            HashT nextHash = hasher.hashCode();

            if(seenHashes.count(nextHash))
            {
                return s.substr(i, targetLen);
            }
            seenHashes.insert(nextHash);
        }

        return std::nullopt;
    }
    size_t longestDupSubstringSize(const string& s)
    {
        size_t minSize = 0, maxSize = s.size();

        size_t longestFoundSize = 0;

        while(minSize <= maxSize)
        {
            size_t midSize = (minSize + maxSize) / 2;

            if(dupSubstringExists(s, midSize))
            {
                longestFoundSize = midSize;
                minSize = midSize + 1;
            }
            else
            {
                maxSize = midSize - 1;
            }
        }
        return longestFoundSize;
    }
private:
    void testDupSubstringExists()
    {
        assert(dupSubstringExists("abab", 2));
        assert(!dupSubstringExists("aba", 2));
        assert(dupSubstringExists("aa", 1));
        assert(dupSubstringExists("zabcdabcdaz", 5));
        assert(!dupSubstringExists("nnpxouomcofdjuujloanjimymadkuepightrfodmauhrsy", 3));
    }
public:
    string longestDupSubstring(string s) {
        //testDupSubstringExists();

        size_t longestDupSubstr = longestDupSubstringSize(s);

        std::cout << "longest dup substr: " << longestDupSubstr << std::endl;
        auto res =  getDupSubstring(s, longestDupSubstr);
        if(!res.has_value())
        {
            throw std::runtime_error{"issue in longestDupSubstringSize"};
        }
        return *res;
    }
};
296420