CodeForces - 1183E Subsequences(easy version)(문자열 bfs)

The only difference between the easy and the hard versions is constraints.
A subsequence is a string that can be derived from another string by deleting some or no symbols without changing the order of the remaining symbols. Characters to be deleted are not required to go successively, there can be any gaps between them. For example, for the string "abaca"the following strings are subsequences: "abaca", "aba", "aaa", "a"and ""(empty string). But the following strings are not subsequences: "aabaca", "cb"and "bcaa".
You are given a string ss consisting of nn lowercase Latin letters.
In one move you can take any subsequence tt of the given string and add it to the set SS. The set SS can't contain duplicates. This move costs n−|t|n−|t|, where |t||t| is the length of the added subsequence (i.e. the price equals to the number of the deleted characters).
Your task is to find out the minimum possible total cost to obtain a set SS of size kk or report that it is impossible to do so.
Input
The first line of the input contains two integers nn and kk (1≤n,k≤1001≤n,k≤100) — the length of the string and the size of the set, correspondingly.
The second line of the input contains a string ss consisting of nn lowercase Latin letters.
Output
Print one integer — if it is impossible to obtain the set SS of size kk, print -1. Otherwise, print the minimum possible total cost to do it.
Examples
Input

4 5
asdf

Output

4

Input

5 6
aaaaa

Output

15

Input

5 7
aaaaa

Output

-1

Input

10 100
ajihiushda

Output

233

Note
In the first example we can generate SS = { "asdf", "asd", "adf", "asf", "sdf"}. The cost of the first element in SS is 00 and the cost of the others is 11. So the total cost of SS is 44.
 
 
제목:
길이가 n인 문자열을 주고 그 중 k개의 다른 서열을 찾아내서 대가 (삭제 문자 수) 를 최소화합니다.
아이디어:
만약 dfs를 통해 모든 하위 문자열을 다 찾으면 2^100가지가 가능할 것입니다. 분명히 통하지 않을 것입니다.
문자열을 그림으로 추상화할 수 있으며, 문자는 하나의 노드이다.bfs와 set을 결합하여 대기열은 현재 문자열을 저장하고 한 번에 한 문자를 삭제합니다. set가 존재하지 않으면 대기열과 set을 업데이트합니다.
bfs층은 적은 문자열을 삭제하는 것부터 시작하여 대가의 최소 효율이 가장 우수함을 보장합니다.
 
정부측 문제풀이.

#include 

using namespace std;

int main() {
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
#endif
    
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    
    int ans = 0;
    queue<string> q;
    set<string> st;
    q.push(s);
    st.insert(s);
    while (!q.empty() && int(st.size()) < k) {
        string v = q.front();
        q.pop();
        for (int i = 0; i < int(v.size()); ++i) {
            string nv = v;
            nv.erase(i, 1);
            if (!st.count(nv) && int(st.size()) + 1 <= k) {
                q.push(nv);
                st.insert(nv);
                ans += n - nv.size();
            }
        }
    }
    
    if (int(st.size()) < k) cout << -1 << endl;
    else cout << ans << endl;
    
    return 0;
}