C++, multiset, Time complexity

#include<bits/stdc++.h>

int main()
{
    int n;
    std::cin>>n;
    char st[n];
    getchar();
    for (int i=0; i<n; ++i)
        st[i]=getchar();
    std::multiset<char> s;
    int pos1=0,pos2=n-1;
    for (char c:st) s.insert(c);
    for (int i=0; i<n; ++i) {
        if (s.count(st[i])==1) {
            pos1=i;
            break;
        } else s.erase(s.find(st[i]));
    }
    for (int i=n-1; i>=0; --i) {
        if (s.count(st[i])==1) {
            pos2=i;
            break;
        } else s.erase(s.find(st[i]));
    }
    std::cout<<pos2-pos1+1;
}

I have just summit this code to CodeForces system, and it fail the TL (2s), i dont know why, because n constrain is 10^5. And my code work with O(nlogn). Can u guys help me? Thanks <3<3. Link of problem here : http://codeforces.com/problemset/problem/701/C

Indeed, your algorithm is O(nlogn) but this is not a garantee to not exceed a time limit. Remember that the multiplication constant for a big-O complexity may be too big to keep it under a certain time limit.

You are using a multiset only for keeping a count for each type of Pokemon. You lose much time to erase from that multiset and count again from it. You can do much faster than the multiset:

1. By using a map to keep the count for each type and to update it

2. Better yet, since pokemon types are encoded in single chars, you can use an array of 256 elements to keep track of the count. This way you can avoid the "log(n)" complexity of multiset (and map). Here's a refactored version of your code that should run much faster, and moreover it runs in O(n).

int main()
{
    int n;
    std::cin >> n;
    std::vector<char> st(n);
    std::array<int, 256> count; // we could also use a map if we had a bigger set of types...

    // the way you read the input can also be speeded-up,
    // but I want to focus on speeding up the algorithm
    getchar();
    for (int i=0; i<n; ++i) {
        st[i]=getchar(); ++count[st[i]];
    }

    int pos1=0,pos2=n-1;
    for (int i=0; i < n; ++i) {
        if (count[st[i]] == 1) {
            pos1 = i;
            break;
        } else --count[st[i]];
    }
    for (int i=n-1; i>=0; --i) {
        if (s.count(st[i])==1) {
            pos2=i;
            break;
        } else --count[st[i]];
    }
    std::cout<<pos2-pos1+1;
}