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.

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";
    }
}
We've worked on this challenge in these gyms: modena  padua  milan 
comments powered by Disqus