CF1917B Erase First or Second Letter 题解

chenRenning · 2023-12-25 09:29:24 · 题解

题目大意 ：

给定一个长度为n的字符串s。我们定义两个操作，可以对字符串进行操作：

• 删除字符串的第一个字符；
• 删除字符串的第二个字符。

你的任务是找出通过在初始字符串上任意次数(可能为零)以任意顺序应用给定操作而生成的不同非空字符串的数量。

则可以容易想到的是 当确定保留第一个字符的位置时候当第二个字符在i处保留的时候则后面所有字符都只能保留因此反过来想就是保留下标i-n后缀子字符串的时候前i个字符中有多少个不同字符累加起来就是答案了

#include <bits/stdc++.h>

using namespace std ;

void solve()
{
    string str ; int n ;
    cin >> n >> str ;
    int ans = 0 ;
    set<char> s; 
    for(int i = 0 ; i < n ; i++)
    {
        s.insert( str[i] ) ;
        ans += s.size() ; 
    }
    cout << ans << '\n' ;
}

int main()
{
    ios::sync_with_stdio(false) ; cin.tie(0) ; cout.tie(0) ;

    int t = 1 ; cin >> t ;
    while ( t-- ) solve() ;
    return 0 ;
}