# L15-CountDistinctSlices
###### tags: `Codility_lessons`
## Question
https://app.codility.com/programmers/lessons/15-caterpillar_method/count_distinct_slices/
## Key
## Reference
## Solution
### My solution with set (Correct but TIMEOUT happened)

#include<set>
int solution(int M, vector<int> &A) {
    int maxSlice = 1000000000;
    set<int> st;
    int slow = 0;
    int cnt = 0;
    while(slow < A.size())
    {
        for(int i = slow; i < A.size(); i++)
        {
            if(st.find(A[i]) == st.end())
            {
                st.insert(A[i]);
                cnt++;
            }
            else 
            {
             break;
            }
        }
        slow++;
        st.clear();
    }
    if(cnt > maxSlice)
    {
        return maxSlice;
    }
    else
    {
        return cnt;
    }
}

**Reduce to one loop but still TIMEOUT**

#include<set>
int solution(int M, vector<int> &A) {
    int maxSlice = 1000000000;
    set<int> st;
    int slow = 0;
    int fast = 0;
    int cnt = 0;
    while(slow < A.size() || fast < A.size())
    {

        if(st.find(A[fast]) == st.end() && fast < A.size())
        {
            st.insert(A[fast]);
            cnt++;
            fast++;
        }
        else 
        {
            slow++;
            fast = slow;
            st.clear();
        }
    }

    
    if(cnt > maxSlice)
    {
        return maxSlice;
    }
    else
    {
        return cnt;
    }
}

### Solution with two pointer

int solution(int M, vector<int> &A) {
    int count = 0;
    const int max_count = 1'000'000'000;
    auto begin = A.begin();
    auto end = A.begin();
    vector<bool> visited(M + 1, false);
    while (end < A.end() && begin < A.end()) {
        if (visited[*end]) {
            visited[*begin] = false;
            begin++;
        }
        else {
            //calc count
            count += end - begin + 1;
            visited[*end] = true;
            if (end + 1 < A.end())
                end++;
            else
                begin++;
        }
        if (count > max_count)
            return max_count;
    }
    return min(count, max_count);
}