1183E - Subsequences (easy version) - CodeForces Solution

//
// Created by code_of_thrones on 30/3/23
// Ramadan Kareem

// #define all(x) (x).begin(), (x).end()
#define yes cout << "YES\n";
#define no cout << "NO\n";
#define fr(n) for(ll i = 0 ; i < n ; i++)
#define frj(n) for(ll j = 0 ; j < n ; j++)
#define ll long long
#define files    freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
#define code_of_thrones ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#include <bits/stdc++.h>

const ll mod = 3e9 + 7;

using namespace std;


ll gcd(ll a, ll b){
    if(b == 0) return a;
    return gcd(b, a%b);
}

bool isPalindrome(string s){
    ll l = 0, r = s.size()-1;
    while (l <= r)
    {
        if(s[l] != s[r]){
            return false;
        }
        l++, r--;
    }
    return true;
}

ll sum(string& s){
    ll n = s.size();
    ll sum = 0;
    for(int i = 0; i < n; i++){
        sum+= s[i] - '0';
    }
    return sum;
}

vector<ll> facts;

void compFacts(ll n){
    facts.clear();
    ll fact = 2;
    ll i = 3;
    while (fact <= n)
    {
        fact*= i;
        facts.push_back(fact);
        i++;
    }
}

ll cntBin(ll n){
    ll ans = 0;
    while (n > 0)
    {
        ans+= n%2;
        n/= 2;
    }
    return ans;
}


int dx[] = {1, 0, -1, 0, -1, -1, 1, 1};
int dy[] = {0, 1, 0, -1, -1, 1, -1, 1};
char di[] = {'D', 'R', 'U', 'L'};

ll n;
vector<vector<ll>> adj;

// bool valid(int x, int y){
//     return x < n && x >= 0 && y < m && y >= 0 && matrix[x][y] != '#';
// }

const unsigned ll N = 3e5;

bool prime[N+1];
vector<ll> primes;

void sieve(){
    memset(prime, true, sizeof(prime));
    prime[1] = true;
    prime[2] = true;
    for(int p = 2; p * p <= N; p++){
        if(prime[p]){
            for (int i = p * p; i <= N; i += p){
                prime[i] = false;
            }
        }
    }
}


void solve(){
    ll n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    queue<string> q;
    unordered_map<string, bool> visited;
    q.push(s);
    ll ans = 0;
    while (!q.empty() && k > 0)
    {
        string curr = q.front();
        q.pop();
        k--;
        int cn = curr.size();
        ans+= n-cn;
        for(int i = 0; i < cn; i++){
            string tmp;
            for(int j = 0; j < cn; j++)if(j != i) tmp+= curr[j];
            if(!visited[tmp]){
                visited[tmp] = true;
                q.push(tmp);
            }
        }
    }
    if(k > 0){
        cout << -1;
        return;
    }
    cout << ans;
}

int main() {
    code_of_thrones
    // files
    ll t = 1;
    // cin >> t;
    while(t--){
        solve();
    }
    return 0;
}