We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Practice
  2. Algorithms
  3. Strings
  4. Gemstones
  5. Discussions

Gemstones

  • sidmeister + 4 comments

    Instead of checking it against all 26 alphabet, find the shortest of the strings, make a set out of those letters in the shortest string and compare.

    • youranjoy + 2 comments

      Then you need to store all the strings and find the minimal. It's a sacrifice of space.

      • boris93 + 0 comments

        or use the first string itself

      • rahul_30213021 + 0 comments

        Space is never a problem in today's world, time is. So always use space whenever u can to save time.

    • off99555 + 1 comment

      The fastest solution is O(n) and it requires only 26 bit slots for storage. There is no need to find the shortest string which will make the process takes longer time. O(n) is already the fastest solution because you need to read every characters.

      • etayluz + 15 comments

        C solution:

        int main() {

    int rocks;
    scanf("%d", &rocks);
    char letter[26] = {0};
    int count = 0;
    for (int r = 0; r < rocks; r++) {
        char s[100];
        scanf("%s", s);
        for (int i = 0; i < strlen(s); i++) {
            char c = s[i];
            if (letter[c - 'a'] == r) {
                letter[c - 'a']++;
                if (letter[c - 'a'] == rocks) {
                    count++;
                }                    
            }
        }
    }

    printf("%d", count);

    return 0;
}

        • santhakumarkrish + 5 comments

          if (letter[c - 'a'] == r) { letter[c - 'a']++; if (letter[c - 'a'] == rocks) { count++; }
          can you explain this concept??

          • Ascalon009 + 0 comments

            Yeah please.

          • adorabilis + 0 comments

            row1: abb row2: a ______I dont think it will pass. Since you even count the letter in the same row. Actually to see if the nubmers of the letter equals the row, is not precise.

          • rocketspacer + 0 comments

            He is counting the letters occurrence in each string, the first condition ensure that same letters in the same string will only be counted once. The second condition is just confirming the answer: if a letter have n counts accross n strings -> number of gem-element increases

          • Vans001 + 0 comments

            r is 0 for first string , first condition "if (letter[c - 'a'] == r) { letter[c - 'a']++;" will increase the letter's index only once throught the whole string if a particular character occures even multiple times. and second condition if (letter[c - 'a'] == rocks) { count++; } means if the particular index is equals to the number of string entered means it's present in every string so increase the counter.

          • chesler + 0 comments

            I like this. People have already explained how duplicates are avoided. I particularly like the other feature (because I had to think about it to understand it), 

            if (letter[c - 'a'] == r) {

            means if up until now we have found this element in as many rocks as we have examined before this rock, it's still a gem-element, so it remains one after this rock as well.

            But I don't like having

            if (letter[c - 'a'] == rocks) {
                    count++;
                }

            inside every every rock since it can only be true when r == rocks-1. I'd prefer to keep s[] outside the outer loop, and after all the rocks have been parsed, go through all the elements in the last rock again, counting if they have been found exactly rock times (and incrementing their count, so they aren't double-counted for duplicate elements in the last rock.)

        • sagar_code + 1 comment

          how you are eliminating the condition of repeated character in the string??

          • ace_dexter + 0 comments

            Have a close look at it:

            "if (letter[c - 'a'] == r) { letter[c - 'a']++; "

            If repeated character is met, this 'if' condition will fail because at first, if condition is passed but after it the letter[c - 'a'] is incremented, but the r's value is still same say '0' for 1st iteration then letter[c - 'a'] will be 1 which leads to failing of this 'if' case for 2nd iteration.

        • prak1ar + 3 comments

          can i marry ur brain?

          • mahtab_alam + 0 comments

            i also want to join...

          • dfdqzp + 0 comments

            My mother tongue is not english.

            Who can tell me what's meaning of this sentence？

          • abhinavsinghraj1 + 0 comments

            hahahaha

        • nazzak + 0 comments

          nice!

        • rajesh503 + 0 comments

          Nice logic

        • Vans001 + 0 comments

          really nice logic.............

        • deeraj_soman + 2 comments

          Nice logic. I modified your logic a bit. First deleted all the repeated elements and them made the comparison. C++ code

          int alpha[26] = {0};
int cnt = 0;
vector <string> str(N);
for(int i = 0; i < N; i++)
{
    cin >> str[i];
    sort(str[i].begin(), str[i].end());
    str[i].erase(unique(str[i].begin(), str[i].end()), str[i].end());

    for(int k = 0; k < str[i].size(); k++)
    {
        char c = str[i].at(k);
        alpha[c - 'a']++;
        if(alpha[c - 'a'] == N)
            cnt++;
    }
}

          • MIC0DE + 0 comments

            char c = str[i].at(k); alpha[c - 'a']++;

            can be simplify to

            alpha[str[i].at(k)-'a']++

            can you explain why int alpha[26] = {0}; has to have a size when I change it to vector? vector alpha(26), without the size the program failed to run.

          • baibhavgunner + 0 comments

            Why is sorting necessary here?

        • spambot + 0 comments

          Very clever the count the rocks on the last iteration of the loop, saving one additional iteration!

        • Black_Dream + 0 comments

          Nice optimise solution.

        • naveenchopra933 + 0 comments

          by this condition we can find only how many a and b etc

        • zeyad1998 + 0 comments

          Very Nice Logic !

        • aniljhajharia + 0 comments
          [deleted]

        • aniljhajharia + 0 comments

          love it man!!!

        • kpa_rukmangatha1 + 0 comments

          i love this letter[26]. i used [123].

        • one_step_ahead + 0 comments

          I was literally scratching my head on finding ways to stop the hash array to stop counting the duplicate characters in the string. You are a genius.

    • decebal4art + 1 comment

      it's a good point about finding the shortest of the strings, but the tests here appear not to deal with that problem, but it is a nice approach in some cases

      • kilgonsa + 0 comments

        what am i doing wrong????

        #include <bits/stdc++.h>

using namespace std;

int main(){
    int n;
    cin>>n;
    vector <vector<int>> a(n,vector<int> (26));
    
    int j=0;
    while(j<n){
        string s;
        cin>>s;
        for(int i=0;i<s.size();i++){
            a[j][s[i]-'a']=1;
        }
        j++;
    }

    int result =0;

    for(int i=0;i<26;i++){
        int c=0;
        for(int k=0;i<n;k++){
            if(a[k][i]==1){
                c++;
            }
        }
        if(c==n){
            result++;
        }
    }
    cout<<result;
    return 0;
}

    • mateusz_szczygi1 + 0 comments

      Thank you kind sir, that's how tips should be passed on, inspired by your advice:

      int gemstones(vector <string> arr){
    set<char> occ;
    for (char c : arr.at(0)) {
        occ.insert(c);
    }
    for (int i=1; i<arr.size(); i++) {
        for (auto c : occ) {
            if (arr.at(i).find(c) == string::npos) {
                occ.erase(c);
            }
        }
        if (occ.size() == 0) break;
        }
 return occ.size();
}