CODEWITHSUNDEEP
c++stringalgorithmperformanceoptimization
groove
groove

Reputation: 43

Count number of different characters between two strings of equal length

I have got two strings of equal length. Each string contains digits '1' to '9'.

I want to calculate the number of indexes where the character at that index is same between the two strings.

Example:

A = "1322113" and
B = "2312213"

then the output should be 4 as characters at 1st, 3rd, 5th and 6th index are same (considering 0 based indexing).

I know about the naive solution of iterating and checking {O(n)}. Is there any library or technique which can give me better time complexity?

Upvotes: 1

Views: 1998

Answers (3)

Vlad from Moscow
Vlad from Moscow

Reputation: 311088

The optimal solution is O( n ) because in any case you have to traverse the both strings to apply an operation to corresponding characters or to check the result of an applied operation to the strings.

As for the concrete solution of the task I can suggest to use the standard algorithm std::inner_product.

For example

#include <iostream>
#include <string>
#include <functional>
#include <iterator>
#include <numeric>

int main() 
{
    std::string s1 = "1322113";
    std::string s2 = "2312213";
    
    auto n = std::inner_product( std::begin( s1 ), std::end( s1 ),
                                 std::begin( s2 ),
                                 size_t( 0 ),
                                 std::plus<>(),
                                 std::equal_to<>() );
                                 
    std::cout << "n = " << n << '\n';
    
    return 0;
}

The program output is

n = 4

If you want to count the number of non-equal characters in the same positions then instead of the function object std::equal_to use std::not_equal_to

Upvotes: 1

Alex Aparin
Alex Aparin

Reputation: 4522

If you want to get better results, then you should consider different approaches for string's storage. The first optimization I see is to keep string as pieces of numbers. Then you can iterate over such numbers, and compare them (if numbers are small, you can use precomputed table of results). The benefits of such approach is too vague (O(N) complexity will become (O(N / constant) ~ O(N)). But for educational purposes you can try to improve algorithm

Upvotes: 0

Stefan Gheorghe
Stefan Gheorghe

Reputation: 59

You cannot obtain a better complexity than the size of the input, in this case N characters. Since you need to check all N characters (as each of them can be a potential solution) the linear O(N) solution of checking all of them is already optimal.

Hope this helps.

Upvotes: 2

Related Questions