<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:
    struct sinfo {
        char ch{0};
        std::deque<int> seg = {};
        int last_i{0};
        void show() {
            std::string ss;
            for (auto i : seg) {
                ss += " " + std::to_string(i);
            }

            std::cout << "ch = " << ch << " vec = {" << ss << "} last_i = " << last_i << std::endl;
        }
    };

    std::map<char, sinfo> cseg;
    int lengthOfLongestSubstring(string s) {
        int i = 0;
        for (auto st : s) {
            std::map<char, sinfo>::iterator it = cseg.end();
            if ((it = cseg.find(st)) == cseg.end()) {
                cseg[st] = sinfo{st, std::deque<int>{i}, 0};
            } else
                cseg[st].seg.push_back(i);
            
            //cseg[st].show();
            i++;
        }

        int top_len = 0;
        
        for (int idx = 0; idx < s.length(); ++idx) {

            int this_len = s.length() - idx;;
            std::map<char, sinfo>::iterator it = cseg.begin();
            while (it != cseg.end()) {
                sinfo &sr = it->second;

                //trim items we surpased
                while (!sr.seg.empty()) {
                    if (sr.seg.front() < idx) {
                        sr.seg.pop_front();
                    } else 
                        break;
                }

                if (sr.seg.empty() || sr.seg.size() == 1) { //this letter can go all the way, does not matter
                    it++;
                    continue;
                }

                std::deque<int>::iterator nextitem_it = sr.seg.begin();
                nextitem_it++;
                int current_letter_max = *nextitem_it - idx;
                if (current_letter_max < this_len)
                    this_len = current_letter_max;

                it++;
            }

            if (this_len > top_len)
                top_len = this_len;
             
             it++;

        }



        return top_len;
    }
};
48083