それぞれの文字の出現回数を$ cnt_iに保存しておく $ dp[i][j] として文字を$ i種類使って$ j文字にしたときの場合の数とする 遷移は$ i \gt 0 で$ dp[i][j] = \sum_k^{cnt_i} {}_{j}C_{k} dp[i-1][j-k] j-k文字あるところに同じ文字k文字を入れるのは$ {}_jC_k通りあるため 答えは$ \sum_j^{|S|}dp[2