Simple C++ solution using a map and a set


#1
#define MOD 1000003
int factorial(int x) {
    int result = 1;
    for(int i = 2; i <= x; i++) {
        result = ((result % MOD) * (i % MOD)) % MOD;
    }
    return result;
}

int Solution::findRank(string A) {
    string B = A;
    sort(B.begin(), B.end());
    
    // map to store char and characters less than it
    unordered_map<char, int>m;
    for(int i = 0; i < B.length(); i++) {
        m[B[i]] = i;
    }
    
    // to keep track of chars used
    unordered_set<char>s;
    
    int result = 1;
    for(int i = 0; i < A.size(); i++) {
        // to mark current character is used
        s.insert(A[i]);
        int charsLessThanThis = m[A[i]];
        int temp = charsLessThanThis;
        for(int i = 0; i < temp; i++) {
            if (s.find(B[i]) != s.end()) {
                charsLessThanThis--;
            }
        }
        result = ((result % MOD) 
                + ((charsLessThanThis * factorial(A.size() - 1 - i)) % MOD))
                % MOD;
    }
    return result;
}