CodeSignal #4

commonCharacterCount.cpp

#include <string>
#include <iostream>
#include <map>
#include <utility>


using namespace std;

int solution(string s1, string s2)
{
    map<char, int> charLastposMap{};
    int matches{};
    
    for (auto ch : s1)
    {
        // set the position in s2 from where we will start to look for a matching character
        constexpr int novalue = -1;
        auto pos = novalue;
        auto it = charLastposMap.find(ch);
        
        if (it != charLastposMap.end())
            pos = it->second;
        
        // Look for the character in s2
        auto posfound = s2.find(ch, pos + 1);
        
        if (posfound == s2.npos)
            continue;
        
        matches++;
        
        // 
        if (pos == novalue)
            charLastposMap.emplace(make_pair(ch, posfound));
        else
            charLastposMap[ch] = posfound;
    }
    return matches;
}

int main()
{
    string one = {'a', 'a', 'c', 'c', 'a'};
    string two = {'a', 'd', 'c', 'b', 'a'}; 
    cout << "Matches: " << solution(one, two) << "\n";
}