String Construction

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.

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 #include using namespace std; int main() { int n; cin >> n; string str; while (n--) { cin >> str; set 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 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 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"; } } 
We've worked on this challenge in these gyms: modena  padua  milan  turin