See the original problem on HackerRank.
Solutions
Intuition: we only pay the number of distinct letters in s. The rest can be copied.
Thus, the solution consists in simply counting the number of distinct characters in s.
Haskell
Just use Set to count unique characters.
1
2
3
4
5
6
7
8
9
|
import qualified Data.Set as Set
import Data.List (intercalate)
calculateCost = length . Set.fromList
main = do
_ <- getLine
contents <- getContents
putStrLn . intercalate "\n" $ show . calculateCost <$> lines contents
|
C++
Very similar to Haskell, we can use a std::set:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
#include <set>
#include <iostream>
using namespace std;
int main()
{
int n; cin >> n;
string str;
while (n--)
{
cin >> str;
set<char> s(begin(str), end(str));
cout << s.size() << "\n";
}
}
|
This solution is really generic: we can even include characters that are not in the problem domain.
Alternatively, for performance, we can bound the solution to the problem domain by using a static table of characters:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
#include <iostream>
int main()
{
int n; std::cin >> n;
std::string str;
while (n--)
{
int count = 0;
bool occurrences[26] = {};
std::cin >> str;
for (char c : str)
{
const int index = c - 'a';
count += occurrences[index] == false;
occurrences[index] = true;
}
std::cout << count << "\n";
}
}
|
Exercise: refactor the code by using count_if.
A further optimization consists in stopping when all the characters (26) are found in the input string is reached:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
#include <iostream>
int main()
{
int n; std::cin >> n;
std::string str;
while (n--)
{
int count = 0;
bool occurrences[26] = {};
std::cin >> str;
for (char c : str)
{
const int index = c - 'a';
if (!occurrences[index])
{
occurrences[index] = true;
if (++count == 26)
break;
}
}
std::cout << count << "\n";
}
}
|