3906. Count Good Integers on a Grid Path

You are given two integers l and r, and a string directions consisting of exactly three 'D' characters and three 'R' characters.

For each integer x in the range [l, r] (inclusive), perform the following steps:

• If x has fewer than 16 digits, pad it on the left with leading zeros to obtain a 16-digit string.
• Place the 16 digits into a 4 × 4 grid in row-major order (the first 4 digits form the first row from left to right, the next 4 digits form the second row, and so on).
• Starting at the top-left cell (row = 0, column = 0), apply the 6 characters of directions in order:
  • 'D' increments the row by 1.
  • 'R' increments the column by 1.
• Record the sequence of digits visited along the path (including the starting cell), producing a sequence of length 7.

The integer x is considered good if the recorded sequence is non-decreasing.

Return an integer representing the number of good integers in the range [l, r].

unordered_map<long long, long long> dp[16];
class Solution {
    long long helper(string& s, vector<int>& at, int pos, int lookup, int prv, bool less) {
        if(pos == s.length()) return 1;
        if(!less) {
            if(pos == at[lookup]) {
                long long res = 0;
                for(int i = prv; i < s[pos] - '0'; i++) {
                    res += helper(s,at,pos+1,lookup+1,i,true);
                }
                if(prv <= s[pos] - '0') {
                    res += helper(s,at,pos+1,lookup+1,s[pos]-'0',false);
                }
                return res;
            } else {
                long long res = 0;
                for(int i = 0; i < s[pos] - '0'; i++) {
                    res += helper(s,at,pos+1,lookup,prv,true);
                }
                res += helper(s,at,pos+1,lookup,prv,false);
                return res;
            }
        } else {
            if(dp[pos].count(prv)) return dp[pos][prv];
            long long& res = dp[pos][prv] = 0;
            if(pos == at[lookup]) {
                for(int i = prv; i <= 9; i++) {
                    res += helper(s,at,pos+1,lookup+1,i,less);
                }
            } else {
                res = 10 * helper(s,at,pos+1,lookup,prv,less);
            }
            return res;
        }
    }
    long long helper(long long n, string& d) {
        string s = to_string(n);
        while(s.length() < 16) s = "0" + s;

        for(int i = 0; i < 16; i++) dp[i].clear();
        vector<int> at{0};
        int y = 0, x = 0;
        for(auto& ch : d) {
            if(ch == 'D') y++;
            else x++;
            at.push_back(y * 4 + x);
        }


        return helper(s,at,0,0,0,false);
    }
public:
    long long countGoodIntegersOnPath(long long l, long long r, string directions) {
        return helper(r, directions) - helper(l-1,directions);
    }
};