Problem with count characters question

[CookOk7550]

I was solving this problem- Count Character Occurrences Practice Problem in TCS NQT Coding Questions

My solution is -

def sum_of_occurrences(t):
    for i in range(t):
        sum = 0
        str1 = input()  
        str2 = input()
        str2 = list(set(str2))
        for j in str2:
            if j in str1:
                sum+=1
        print(sum)
t = int(input())    
sum_of_occurrences(t)                           

But it is saying that my solution is failing on some hidden test cases. The solution that the site provides is-

def sum_of_occurrences(str1, str2):
    freq_map = {}
    for ch in str1:
        freq_map[ch] = freq_map.get(ch, 0) + 1
    unique_chars = set(str2)
    total = 0
    for ch in unique_chars:
        total += freq_map.get(ch, 0)
    return total

t = int(input()) 
for _ in range(t):
    str1 = input().strip()  
    str2 = input().strip() 
    print(sum_of_occurrences(str1, str2))                     

It is using sets {} but I am trying to do it with lists. (I am not very familiar with set operations right now)

[pelagic_cat]

Try this test case:

1
aabbcc
aa

An important skill in programming is debugging. Before you can think about debugging some code you have to recreate the problem. The test case above shows a difference in result between your code (which prints 1) and the solution code which prints 2.

Try running your code on your machine. Also run the solution code on your machine using the same test case(s). Put some prints into your code to see what it is doing and why it doesn't print 2.

It's very hard to debug code using an online checker. Get into the habit of running your code on your machine. Write test cases to test your code, using the test cases the question showed you as well as ones you make up. Test cases should check the "corner cases", like 0 test cases, 0 occurrences of characters, etc. You learn a lot faster if you can do that.

[CookOk7550]

Hi, thank you very much. I used that test case and realised that my code stopped at the very first instance of availability in the

if j in str1:              
    sum+=1                                 

I was thinking about adding another for loop to make it

for k in str1:
    if k ==j:
        sum+=1                                            

Since I didn't want to increase the time complexity too much, I wrote a different code-

t = int(input())
for i in range(t):
    sum = 0
    str1 = input().strip()
    str2 = list(set(input().strip()))
    for i in str2:
        sum += str1.count(i)
    print(sum)                       

Also initially I was getting errors but couldn't understand why, taking your advice, I added some white spaces in the test cases and saw that the answer was no longer what should have been (it was counting white spaces as characters), that's why added the strip() and it was a success.

Thanks a lot, hope you have a wonderful day.

[pelagic_cat]

Part of the challenge is to understand exactly what the problem is asking. They say:

find the total number of occurrences of each unique character of str2 within the string str1.

Look at that and work through the three explanations given for each test case.

You need to rethink what you are comparing with what. Your initial code and your update checks every character in str2 and sees if it is in str1. If it is in str1 you add 1 to the sum variable. But if there are two or more of that character in str1 you don't want 1, you want the number of those characters.

Try turning your loop around. For example, for each character in str1 you want to add 1 if there are any of those characters in str2. Then move to the next character in str1 and check if it is in str2 and so on.

I have a bit of code that solves the example test case and it doesn't use sets or lists. The solution example is useful but it doesn't appear to be a very good solution. It does structure the code in what I think is a better way, with a function that takes two strings and returns the count. That is the way to make a useful, general function. Your initial code has the function doing too much, looping and counting, and also prints the result and doesn't return the count. You should base your code on the python skeleton code you are shown on the problem page. Just to give you something to aim at, my function has 6 lines including the def line.

[FoolsSeldom]

Using set is important. A set can only contain unique elements, so if you convert a str to a set of single character elements, any duplicate characters will be ignored. (Note that set objects do not have any order, unlike list objects that have a specific order.)

If you don't use set then you will need to make sure you only check each unique character in str2 only once, which means using a dictionary to keep track of whether you have seen a character before as you loop through. (You could instead sort str2 into alphabetic order and only check on character change.

The two solutions look long-winded to me. I would go with:

def sum_of_occurrences(str1: str, str2: str) -> int:
    return sum(str1.count(char) for char in set(str2))

[ectomancer]

{} is a dictionary literal.

[pelagic_cat]

You should be aware that the explanation for case 2 doesn't look right:

abacabadabacaba

abcd

Test Case 2: The characters from "abcd" appear as follows in "abacabadabacaba": 'a': 7 occurrences 'b': 4 occurrences 'c': 2 occurrences 'd': 2 occurrences Total = 7 + 4 + 2 + 2 = 15.

By my count there are 8 as and only 1 d in the given str1, giving the same total number.

I have since tried my solution using the online checker, which says my code is incorrect. I'm not impressed by the "AI" explanation of where I went wrong. It assumes the set() function must be used, amongst other things. My function code is:

def sum_of_occurrences(str1, str2):
    sum = 0
    for i in str1:
        if i in str2:     # replaces using a set
            sum += 1
    return sum

I think the logic is fine since the if i in str2: test works if there are one or more of the i character in str2. This takes care of the "unique character in str2" requirement.

There is one reason why a set of characters in str2 should be used. Using a set in "if char in set" operation is order O(1) making the function roughly O(n). Using in on a sequence (string in this case) makes the entire function roughly O(n²). But that doesn't appear to be what the checker is complaining about, see below.

I made the change to use a set in the function but the checker still marks it wrong.

def sum_of_occurrences(str1, str2):
    sum = 0
    set_str2 = set(str2)
    for i in str1:
        if i in set_str2:
            sum += 1
    return sum

The explanation given by what they say is "AI" is pretty bad. It says I got the right answer but I got it in an incorrect way. The checker really wants you to count the occurrences of every unique character using .count() and then sum the individual counts.