Number of times characters of a string is present in another string


This problem is one of the classic competitive questions dealing with strings, I guess we can understand the logic by the question itself, so we will be given with two strings, the main string and the sample string. Now we need to compare and check how many times a charachter in the main string appers int the other i.e the count and finally in the end we need to return the total number. Now let's work on the implementation part but before we proceed please note that each and every character of the first string should be unique, having duplicates will simply double the count for no reason.

Example :

Input
String 1: aA
String 2: aaaAAA
Output : 6

# 'a' and 'A' occurs 3 times each in string 2

Input
String 1: abBAc
String 2: cZZz
Output : 1

# 'c' occurs 1 time in string 2, others never occur.

Solution Approach

The solution for this problem can be obtained by comparing each charcter in string 1 with all characters in string 2 and update the count value each and every time they match and at last display the total sum of all occurances.

Steps

  1. Iterate through each character in the string 1
  2. Now for one iteration in string 1 we need to iterate through all the characters in string 2
  3. For every match/occurance of the characters i.e when both are same increment the count value
  4. Repeat this process until all charcters in string 1 are iterated
  5. Finally display the total value.

Explanation

  • Iteration through the whole string 1 can be done with the help of a simple for loop till the end i.e size/length of the string but we need to nest another loop inside this to iterate through all the characters in string 2 also.

  • For comparing the characters the process is simple as it does not matter whether the characters are capital or small because we are comparing all of them using ' == ' so it is only validated unless and until they are the same.

  • Finally while iterating we store the count value in a seperate variable and increment it each time there's a match, and print it in the end as that is our answer.

Pseudocode

  1. Start
  2. Read String 1 and store it.
  3. Read String 2 and store it.
  4. pass both the strings to a function/loop to start comparing
  5. Initialize a seperate variable to store answer values
  6. Now start iterating throught string 1 and compare with all the characters in string 2.
  7. For every match increment the count value
  8. Repeat this for all characters in string 1
  9. At last print the count value
  10. Exit.

Program in C++

#include <iostream>
using namespace std;

int occur(string a, string b) 
{
        int count=0;
        for(int i=0;i<a.size();i++)
        {
            for(int j=0;j<b.size();j++)
            {
                if(a[i]==b[j])
                    count++;
            }
        }
        return count;
    }
int main()
{
    string a,b;
    cout<<"Enter String 1"<<endl;
    cin>>a;
    cout<<"Enter String 2"<<endl;
    cin>>b;
    int answer=occur(a,b);
    cout<<answer;
    return 0;
}

Example Step by Step Explaination

Input

  • Initial steps read both the strings and store them seperately
string1 = zoe
string2 = opengenus
  • pass both the string to a function

  • First we initialize count = 0 meant to store the count value

  • iteration starts

  • for every character in string 1 we iterate through all the characters in string 2

  • increment the count value if they match

count = 0;
string1 = zoe;
string2 = opengenus;
  • z

  • z == o, z == p, z == e, z== n, z == g, z == e, z == n , z == u, z == s.

  • no matches no increment
    *count= 0

  • o

  • o == o ++, o == p, o == e, o == n, o == g, o == e, o == n , o == u, o == s.

  • one match count++

  • count = 1

  • e

  • e == o ++, e == p, e == e, e == n, e == g, e == e, e == n , e == u, e == s.

  • two match count+2

  • count = 3

  • all characters in string 1 have been iterated

  • display the count value

  • count = 3

End

Thoughts and different approaches

This is a standard string comparision problem, it's a bit easy as there are no constraints and conversios and all characters are compared directly.There might also be many other ways to solve this problem but in this approach I tried to explain the logic as simple as possible, we can use this logic in similar scenarios and keep exploring and learn new methods. The above method is called as hashmap method for this types of problem we can also try other ways like using dictionaries in python or using minimum index value with Java and any other languages.

With this article at OpenGenus, you must have the complete knowledge of solving this problem of finding the Number of times characters of a string is present in another string. Enjoy.