Microsoft - # of fragments (optimised), C++ (gcc)

Microsoft - # of fragments (optimised)

//g++  7.4.0

#include <bits/stdc++.h>

using namespace std;

typedef long long int ll;

int MapToInt (char ch) {
    if (ch >= 'a' && ch <= 'z') return (ch - 'a');
    if (ch >= 'A' && ch <= 'Z') return (ch - 'A' + 26);
    return -1;
}

vector<int> Difference (vector<int>& v1, vector<int>& v2) {
    vector<int> result;
    
    for (int j = 0; j < v1.size(); j ++) {
        result.push_back (v1[j] - v2[j]);
    }
    return result;
}

ll CountOfEqualFragments (const string& s1, const string& s2) {
    int n = min (s1.length(), s2.length());
    
    ll ans = 0;
    vector<int> f_s1(52), f_s2(52);
    map<vector<int>, int> freq;
    
    freq[Difference(f_s1, f_s2)] = 1;
    
    for (int j = 0; j < n; j ++) {
        f_s1 [MapToInt(s1[j])] ++;
        f_s2 [MapToInt(s2[j])] ++;
        
        int &current_frq = freq[Difference(f_s1, f_s2)];
        
        ans += current_frq;
        current_frq ++;
    }
    
    return ans;
}

int main() {
    string s1 = "dBacaAA";
    string s2 = "caBdaaA";
    
    cout << CountOfEqualFragments (s1, s2) << endl;
    return 0;
}


run \| edit \| history \| help	0

λ

                                      .NET NoSQL database for rapid development