Lweb and String

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 122    Accepted Submission(s): 83 Problem Description Lweb has a string  S . Oneday, he decided to transform this string to a new sequence.  You need help him determine this transformation to get a sequence which has the longest LIS(Strictly Increasing).  You need transform every letter in this string to a new number. A  is the set of letters of  S ,  B  is the set of natural numbers.  Every injection  f:A→B  can be treat as an legal transformation.  For example, a String “aabc”,  A={a,b,c} , and you can transform it to “1 1 2 3”, and the LIS of the new sequence is 3.   Now help Lweb, find the longest LIS which you can obtain from  S . LIS: Longest Increasing Subsequence. (https://en.wikipedia.org/wiki/Longest_increasing_subsequence)   Input The first line of the input contains the only integer  T,(1≤T≤20) . Then  T  lines follow, the i-th line contains a string  S  only containing the lowercase letters, the length of  S  will not exceed  105 .   Output For each test case, output a single line "Case #x: y", where x is the case number, starting from 1. And y is the answer.   Sample Input 2 aabcc acdeaa   Sample Output Case #1: 3 Case #2: 4   Author UESTC   Source 2016中国大学生程序设计竞赛 - 网络选拔赛    Recommend wange2014   |   We have carefully selected several similar problems for you:   5842  5841  5840  5839  5838  // // main.cpp // Lweb and String // // Created by 张嘉韬 on 16/8/14. // Copyright © 2016年 张嘉韬. All rights reserved. // #include <iostream> #include <cstdio> #include <map> using namespace std; const int maxn=100000+10; int main(int argc, const char * argv[]) { //freopen("/Users/zhangjiatao/Documents/暑期训练/input.txt","r",stdin); int T; scanf("%d",&T); for(int t=1;t<=T;t++) { map<char,int> vis; vis.clear(); int counter=0; char str[maxn]; scanf("%s",str); for(int i=0;str[i];i++) { if(vis[str[i]]==1) continue; else { vis[str[i]]=1; counter++; if(counter>=26) break; } } printf("Case #%d: %d\n",t,counter); } return 0; }