fzu2218

dp[t]는 t 상태의 모든 서브집합의 최대 길이를 나타낸다

#include <iostream>
#include <string>
#include <string.h>
#include <vector>
#include <stdio.h>
#include <algorithm>
#include <map>
#include <math.h>
typedef long long LL ;
const int N = 2008 ;
char word[N] ;
int  dp[(1<<16) + 8] ;

int  main(){

     std::ios::sync_with_stdio(false) ;

     int t , n , k  , limit ;
     scanf("%d" , &t) ;
     while(t--){
        scanf("%d%d" , &n , &k) ;
        scanf("%s" , word) ;
        limit = (1<<k) - 1 ;

        memset(dp , 0 , sizeof(dp)) ;

        for(int st = 0 ; st < n ; st++){
            int state = 0 ;
            for(int ed = st ; ed < n ; ed++){
                state |= (1<< (word[ed] - 'a')) ;
                dp[state] = std::max(dp[state] , ed - st + 1) ;
            }
        }


        for(int state = 0 ; state <= limit ; state++){
             for(int i = 0 ; i < k ; i++){
                if(state & (1 << i)){
                    dp[state] = std::max(dp[state] , dp[state ^ (1<<i)]) ;
                }
             }
        }

        int  res = 0 ;
        for(int state = 0 ; state <= limit ; state++){
            res = std::max(res , dp[state] * dp[limit ^ state]) ;
        }
        std::cout<< res << std::endl ;

     }


     return 0  ;
}