首先可以证明，只由一种字符构成的串总会是最优解中的一种。。。

    考虑随便一个T与S的LIS都至少是出现次数最少的字符个数(考虑反证法，如果要更短，那么T中每种字符的个数都至多是 S 中最少的字符个数-1，最后长度肯定不到N)，于是我们就拿出现次数最少的字符填成T就行了。。。

 

#include
     
      #define ll long longusing namespace std;int cnt[26],ans=1e9;char ch;int main(){	for(ch=getchar();ch>='a'&&ch<='z';ch=getchar()) cnt[ch-'a']++;	for(int i=0;i<26;i++) ans=min(ans,cnt[i]);	printf("%d\n",ans);	return 0;}