<p>Given a string <code>s</code>, find the length of the <strong>longest</strong> <span data-keyword="substring-nonempty"><strong>substring</strong></span> without repeating characters.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;abcabcbb&quot;
<strong>Output:</strong> 3
<strong>Explanation:</strong> The answer is &quot;abc&quot;, with the length of 3.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;bbbbb&quot;
<strong>Output:</strong> 1
<strong>Explanation:</strong> The answer is &quot;b&quot;, with the length of 1.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;pwwkew&quot;
<strong>Output:</strong> 3
<strong>Explanation:</strong> The answer is &quot;wke&quot;, with the length of 3.
Notice that the answer must be a substring, &quot;pwke&quot; is a subsequence and not a substring.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>0 &lt;= s.length &lt;= 5 * 10<sup>4</sup></code></li>
	<li><code>s</code> consists of English letters, digits, symbols and spaces.</li>
</ul>

class Solution {
public:
	std::unordered_map<std::string, int> cache;
    int NumDuplicates(std::string s)
    {
        auto it = cache.find(s);
        if(it!=cache.end())
                return it->second;
         
        alignas(64)
        char lut[256];

        for(int i=0;i<256;i++)
            lut[i]=0;
        const int n=s.size();
        for(int i=0;i<n;i++)
        {   
            const auto data = lut[(uint8_t)s[i]];
            lut[(uint8_t)s[i]]=data+1;
            if(data == 1)
            {
                
                cache[s]=1; 
                return 1;
            }
        }
        
        cache[s]=0;
        return 0;
    }

    struct Node
    {
        std::string * s;
        int * comp;
        int start;
        int stop;
    };
    std::unordered_map<std::string,bool> posCache;
    void IsWindowValid(std::string * s, int start, int stop,int * comp, const int ctrMax)
    {
        std::queue<Node> q;
        Node root{s, comp, start,stop};
        q.push(root);
        bool exit = false;
        while(q.size()>0)
        {           
            if(exit)
                break;

            auto node = q.front();
            const int len = node.stop-node.start+1;
            q.pop();

            if(len>ctrMax)
                continue;

            auto posStr = std::to_string(node.start) +"_"+std::to_string(node.stop);
            if(posCache.find(posStr)!=posCache.end())
                continue;                
            posCache[posStr]=true;
            
            
            
            const int dup = NumDuplicates(node.s->substr(node.start,len));

            if(!dup)
            {
                if(*node.comp<len)
                    *node.comp=len;

                if(len>=ctrMax)
                    exit=true;
            }

            if(!dup)        
            {
                // left grow
                if(node.start>0)
                {
                    if(posCache.find(std::to_string(node.start-1) +"_"+std::to_string(node.stop))==posCache.end())
                    {
                        Node newNode = node;
                        newNode.start--;
                        q.push(newNode);
                    }
                }
                // right grow
                if(node.stop<node.s->size()-1)
                {
                    if(posCache.find(std::to_string(node.start) +"_"+std::to_string(node.stop+1))==posCache.end())
                    {
                        Node newNode = node;
                        newNode.stop++;
                        q.push(newNode);
                    }
                }
            }
            else
            {
                // left shrink
                if(node.start<node.stop)
                {
                    if(posCache.find(std::to_string(node.start+1) +"_"+std::to_string(node.stop))==posCache.end())
                    {
                        Node newNode = node;
                        newNode.start++;
                        q.push(newNode);
                    }
                }
                // right shrink
                if(node.start<node.stop)
                {
                    if(posCache.find(std::to_string(node.start) +"_"+std::to_string(node.stop-1))==posCache.end())
                    {
                        Node newNode = node;
                        newNode.stop--;
                        q.push(newNode);
                    }
                }

                
            }            
        }


    }

    int lengthOfLongestSubstring(string s) {        
        const int n = s.size();     
        if(n==0)   
            return 0;
        if(n==1)
            return 1;
        if(n==2 && s[0]!=s[1])
            return 2;
        ushort ctr[256];
        for(int i=0;i<256;i++)
            ctr[i]=0;        
        for(int i=0;i<n;i++)
            ctr[s[i]]++;
        
        int ctr2 = 0;
        for(int i=0;i<256;i++)
            ctr2+=(ctr[i]==0);  

        // maximum possible length of unique substring due to amount of histogram of characters
        const int ctr3 = 256 - ctr2;
        int comp=0;
        IsWindowValid(&s,n/2,n/2,&comp,ctr3);
        return comp;
    }
};
75071