けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

CS Academy FII Code #1 B - Sugarel and Substrings

しゃくとり法のいい感じの練習問題

問題へのリンク

問題概要

英小文字のみから成る文字列  S が与えられる。 S の連続する部分文字列のうち「同じアルファベットが2度以上使われることのない」ものが何個あるかを数えよ (空文字列は 1 個とみなす)

制約

  •  1 \le N \le 10^{5}

考えたこと

しゃくとり法の記事の中の、

「ARC 022 B 細長いお菓子」

とほぼまったく同じ問題

#include <iostream>
#include <string>
#include <set>
using namespace std;

int main() {
    int N;
    string S;
    cin >> N >> S;
    long long res = 0;
    int right = 0;
    set<char> member;
    for (int left = 0; left < N; ++left) {
        while (right < N && !member.count(S[right])) {
            member.insert(S[right]);
            ++right;
        }
        res += right - left;
        if (left == right) ++right;
        else  member.erase(S[left]); // a[left] を削除
    }
    cout << res << endl;
}