2018-3 video sequence ( find the list of size of the each sub sequence )

// reverse algorithm example
#include <iostream>     // std::cout
#include <algorithm>    // std::reverse
#include <vector>       // std::vector
#include <unordered_map>


//key point
// the complexity is (n)
//use the unordered_map< char, last position of this char> to record the last position of each char in string.
//use the slide window to iterate each char in string .
    // <sp , ep> is the slide window. use ep to indicator the last postion of the current substring that is substring< sp, cur >.
    // continue move ‘cur‘ in window, if last postion of char in ‘cur‘ position is large than ep, update the ep to that postion. then the size of the window is changed. if ‘cur‘ ==‘ep‘, the a substring found that meet the requirement of the problem.

using namespace std;

vector<int > findSequenceSize(string& s ){
    if(s.empty()) return {0};
    
    unordered_map <char , int > charPos;
    vector<int > res;
    
    int index =0;
    for ( auto& e : s)
        charPos[e] = index++;
    
    int sp =0; int ep =0; int cur =0;
    
    while ( ep < s.size ()){
        
        ep = charPos[s[ep]]; // find the last index of this char.
        //cout <<" the ep is " << ep<< endl;
        
        if ( ep != sp)
            cur = sp+1;  // more than one char in window.
        else
            goto CONTINUE ;  //only one char taht meet the requirement(in window).
        
        while ( cur != ep){
            int i = charPos[s[cur]];
            if(i > ep){  //adjust the size of the window.
                ep = i;
            }
            cur ++;  // move to the next char in window
        }
        
    CONTINUE :  // find one substring meet the requirment.
        res.push_back(ep - sp +1);
        cout << " the substring is " << s.substr(sp, ep-sp+1)<< endl;
        ep++;
        sp = ep;
        cur =sp;
            
    }
    return res;
    
}

int main () {
    string in = {"abacdfeffhijkik"};
    //string in = {"abcdd"};
    
    auto&& out = findSequenceSize ( in );
    
    for ( auto& e : out )
        cout <<e << " ";
    
    

    return 0;
}