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

Microsoft - # of fragments (semi-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;
}

ll CountOfEqualFragments (const string& s1, const string& s2) {
    int n = min (s1.length(), s2.length());
    
    ll ans = 0;
         
    for (int j = 0; j < n; j ++) {
        vector<int> f_s1(52), f_s2(52);
        int same_count_frq = 52;
        
        for (int k = j; k < n; k ++) {
            int c1 = MapToInt(s1[k]);
            int c2 = MapToInt(s2[k]);
            
            if (f_s1[c1] == f_s2[c1]) same_count_frq --;
            f_s1 [c1] ++;
            if (f_s1[c1] == f_s2[c1]) same_count_frq ++;
           
            if (f_s1[c2] == f_s2[c2]) same_count_frq --;
            f_s2 [c2] ++;
            if (f_s1[c2] == f_s2[c2]) same_count_frq ++;
            
            if (same_count_frq == 52) ans ++;
        }
    }
    
    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