[CodeForces]-672B-Different is Good

[CodeForces]-672B-Different is Good

原題：

B - Different is Good

Time Limit:2000MS Memory Limit:262144KB 64bit IO Format:%I64d & %I64u

Submit

Status

Practice

CodeForces 672B

Appoint description:

Description

A wise man told Kerem “Different is good” once, so Kerem wants all things in his life to be different.

Kerem recently got a string s consisting of lowercase English letters. Since Kerem likes it when things are different, he wants all substrings of his string s to be distinct. Substring is a string formed by some number of consecutive characters of the string. For example, string “aba” has substrings “” (empty substring), “a”, “b”, “a”, “ab”, “ba”, “aba”.

If string s has at least two equal substrings then Kerem will change characters at some positions to some other lowercase English letters. Changing characters is a very tiring job, so Kerem want to perform as few changes as possible.

Your task is to find the minimum number of changes needed to make all the substrings of the given string distinct, or determine that it is impossible.

Input

The first line of the input contains an integer n (1 ≤ n ≤ 100 000) — the length of the string s.

The second line contains the string s of length n consisting of only lowercase English letters.

Output

If it’s impossible to change the string s such that all its substring are distinct print -1. Otherwise print the minimum required number of changes.

Sample Input

Input

2

aa

Output

1

Input

4

koko

Output

2

Input

5

murat

Output

Hint

In the first sample one of the possible solutions is to change the first character to ‘b’.

In the second sample, one may change the first character to ‘a’ and second character to ‘b’, so the string becomes “abko”.

題目大意：就是給定一個字元串，問經過最少多少次修改可以使該字元串的所有子串都不相同。

題目分析：因為是所有子串都不相同，是以隻要有相同的2個字母的時候一階子串就會相同。是以隻要使所有的字母都不相同就可以了。

個人陷阱：發現周遊字元串将對應的字母放入對應的數組位置的時候：

for (int i = ;i<n;i++){
         vis[str[i]-'a']++; 
 }
           

這裡的n指的是str.length()，如果我取i<=n時就會在DEVC++中莫名蹦掉，隻是小于就沒有事，奇怪。

代碼：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<string>
#include<cstring>
using namespace std  ;

int vis[]; //存字母的重複個數

int main()
{
    int len ; 
    cin>>len ; 
    string str ; 
    cin>>str;
    int ans =  ;
    int n = str.length();
    if(len >  ){
        cout<<"-1";
    }
    else if(len>&&len<=){
        for (int i = ;i<n;i++){
         vis[str[i]-'a']++; 
        }
        for(int j =  ; j <  ;j ++){
            if(vis[j]>){
                ans += vis[j]- ;
            }
        }
        cout<<ans;
    }
    else if(len =  ){
        cout<<"0";
    }

     //cout<<vis[0]<<endl; 
    return  ; 
}