In this HackerEarth Good Subsequences problem solution You are given a string S consisting of lowercase alphabets. A good subsequence of this string is a subsequence which contains distinct characters only.
Determine the number of good subsequences of the maximum possible length modulo 10^9 + 7.
In other words, determine the length X of the longest good subsequence and the number of good subsequences of length X modulo 10^9 + 7.
HackerEarth Good Subsequences problem solution.
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "n"
#define int long long
const int N=1e5+5;
const int MOD=1e9+7;
string s;
int f[26];
int32_t main()
{
IOS;
int t;
cin>>t;
while(t--)
{
int ans=1;
cin>>s;
for(auto &ch:s)
f[ch-'a']++;
for(int i=0;i<26;i++)
{
if(!f[i])
continue;
ans*=f[i];
ans%=MOD;
}
cout<<ans<<endl;
}
return 0;
}
Second solution
#ifndef _GLIBCXX_NO_ASSERT
#include <cassert>
#endif
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#endif
// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif
#define ll long long
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define vi vector<int>
#define all(a) (a).begin(),(a).end()
#define F first
#define S second
#define sz(x) (int)x.size()
#define hell 1000000007
#define endl 'n'
#define rep(i,a,b) for(int i=a;i<b;i++)
using namespace std;
string to_string(string s) {
return '"' + s + '"';
}
string to_string(const char* s) {
return to_string((string) s);
}
string to_string(bool b) {
return (b ? "true" : "false");
}
string to_string(char ch) {
return string("'")+ch+string("'");
}
template <typename A, typename B>
string to_string(pair<A, B> p) {
return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <class InputIterator>
string to_string (InputIterator first, InputIterator last) {
bool start = true;
string res = "{";
while (first!=last) {
if (!start) {
res += ", ";
}
start = false;
res += to_string(*first);
++first;
}
res += "}";
return res;
}
template <typename A>
string to_string(A v) {
bool first = true;
string res = "{";
for (const auto &x : v) {
if (!first) {
res += ", ";
}
first = false;
res += to_string(x);
}
res += "}";
return res;
}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
cerr << " " << to_string(H);
debug_out(T...);
}
template <typename A, typename B>
istream& operator>>(istream& input,pair<A,B>& x){
input>>x.F>>x.S;
return input;
}
template <typename A>
istream& operator>>(istream& input,vector<A>& x){
for(auto& i:x)
input>>i;
return input;
}
#ifdef PRINTERS
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif
long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
assert(cnt>0);
if(is_neg){
x= -x;
}
assert(l<=x && x<=r);
return x;
} else {
debug(int(g));
assert(false);
}
}
}
string readString(int l,int r,char endd){
string ret="";
int cnt=0;
while(true){
char g=getchar();
if(g==endd){
break;
}
else if(islower(g)){
cnt++;
ret+=g;
}
else{
assert(false);
}
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
return readInt(l,r,'n');
}
string readStringLn(int l,int r){
return readString(l,r,'n');
}
string readStringSp(int l,int r){
return readString(l,r,' ');
}
void solve(){
int t = readIntLn(1,10);
for(int i = 0; i < t; i++){
string s;
if(i+1 == t) s = readString(1,100000,EOF);
else s = readStringLn(1,100000);
map<char,int>m;
for(auto i:s){
m[i]++;
}
ll res = 1;
for(auto i:m){
res = (res * i.second)%hell;
}
cout << res << endl;
}
}
int main(){
solve();
return 0;
}