Count the Number of Powerful Integers | Leetcode 2999

class Solution {
    #define ll long long
    #define MAX_DIGITS 17
    ll dp[MAX_DIGITS][2];

    // Helper: Check if number should be subtracted based on suffix and digit constraints
    static bool checkSubtract(const string& num_str, ll num_digits, const string& suffix, int limit) {
        if (num_digits < suffix.size()) return false;

        string suffix_of_num = num_str.substr(num_digits - suffix.size());
        bool subtract = stoll(suffix_of_num) < stoll(suffix);

        if(subtract){
            for (int i = 0; i < num_digits - suffix.size(); ++i) {
                if ((num_str[i] - '0') > limit) {
                    subtract = false;
                    break;
                }
            }
        }
        return subtract;
    }

    // Core recursive + memoized function to count valid numbers <= number_str
    ll countValidNumbers(const string& number_str, ll idx, ll max_digits,
                         bool is_tight, int limit, const string& suffix) {
        if (idx == max_digits) return 1;
        if (dp[idx][is_tight] != -1) return dp[idx][is_tight];

        ll low = 0, high;
        ll suffix_len = suffix.size();

        if (idx >= max_digits - suffix_len) {
            ll suffix_idx = idx - (max_digits - suffix_len);
            low = high = suffix[suffix_idx] - '0';
        } else {
            high = is_tight ? min<ll>(limit, number_str[idx] - '0') : limit;
        }

        ll total = 0;
        for (ll digit = low; digit <= high; ++digit) {
            bool new_tight = is_tight && (digit == number_str[idx] - '0');
            total += countValidNumbers(number_str, idx + 1, max_digits, new_tight, limit, suffix);
        }

        return dp[idx][is_tight] = total;
    }

    // Helper to compute number of valid values up to `num_str`
    ll solveUpTo(const string& num_str, ll num_digits, int limit, const string& suffix) {
        memset(dp, -1, sizeof(dp));
        ll result = countValidNumbers(num_str, 0, num_digits, true, limit, suffix);
        if (checkSubtract(num_str, num_digits, suffix, limit))
            result--;
        return result;
    }

public:
    long long numberOfPowerfulInt(long long start, long long finish, int limit, string suffix) {
        ll suffix_val = stoll(suffix);
        string finish_str = to_string(finish);
        string start_str = to_string(start - 1);

        ll finish_digits = finish_str.size();
        ll start_digits = start_str.size();

        ll upto_finish = (finish >= suffix_val) ? solveUpTo(finish_str, finish_digits, limit, suffix) : 0;
        ll upto_start  = (suffix_val < start) ? solveUpTo(start_str, start_digits, limit, suffix) : 0;

        return upto_finish - upto_start;
    }
};

/*
//JAVA
import java.util.Arrays;

class Solution {
    private static final int MAX_DIGITS = 17;
    private long[][] dp;

    private boolean checkSubtract(String numStr, int numDigits, String suffix, int limit) {
        if (numDigits < suffix.length()) return false;

        String suffixOfNum = numStr.substring(numDigits - suffix.length());
        boolean subtract = Long.parseLong(suffixOfNum) < Long.parseLong(suffix);

        if (subtract) {
            for (int i = 0; i < numDigits - suffix.length(); ++i) {
                if ((numStr.charAt(i) - '0') > limit) {
                    subtract = false;
                    break;
                }
            }
        }
        return subtract;
    }

    private long countValidNumbers(String numberStr, int idx, int maxDigits, 
                                  boolean isTight, int limit, String suffix) {
        if (idx == maxDigits) return 1;
        if (dp[idx][isTight ? 1 : 0] != -1) return dp[idx][isTight ? 1 : 0];

        int low, high;
        int suffixLen = suffix.length();

        if (idx >= maxDigits - suffixLen) {
            int suffixIdx = idx - (maxDigits - suffixLen);
            low = high = suffix.charAt(suffixIdx) - '0';
        } else {
            high = isTight ? Math.min(limit, numberStr.charAt(idx) - '0') : limit;
            low = 0;
        }

        long total = 0;
        for (int digit = low; digit <= high; ++digit) {
            boolean newTight = isTight && (digit == numberStr.charAt(idx) - '0');
            total += countValidNumbers(numberStr, idx + 1, maxDigits, newTight, limit, suffix);
        }

        dp[idx][isTight ? 1 : 0] = total;
        return total;
    }

    private long solveUpTo(String numStr, int numDigits, int limit, String suffix) {
        dp = new long[MAX_DIGITS][2];
        for (long[] row : dp) {
            Arrays.fill(row, -1);
        }
        long result = countValidNumbers(numStr, 0, numDigits, true, limit, suffix);
        if (checkSubtract(numStr, numDigits, suffix, limit)) {
            result--;
        }
        return result;
    }

    public long numberOfPowerfulInt(long start, long finish, int limit, String suffix) {
        long suffixVal = Long.parseLong(suffix);
        String finishStr = Long.toString(finish);
        String startStr = Long.toString(start - 1);

        int finishDigits = finishStr.length();
        int startDigits = startStr.length();

        long uptoFinish = (finish >= suffixVal) ? solveUpTo(finishStr, finishDigits, limit, suffix) : 0;
        long uptoStart = (suffixVal < start) ? solveUpTo(startStr, startDigits, limit, suffix) : 0;

        return uptoFinish - uptoStart;
    }
}

#Python
class Solution:
    MAX_DIGITS = 17

    def checkSubtract(self, num_str: str, num_digits: int, suffix: str, limit: int) -> bool:
        if num_digits < len(suffix):
            return False
        
        suffix_of_num = num_str[num_digits - len(suffix):]
        subtract = int(suffix_of_num) < int(suffix)
        
        if subtract:
            for i in range(num_digits - len(suffix)):
                if int(num_str[i]) > limit:
                    subtract = False
                    break
        return subtract

    def countValidNumbers(self, number_str: str, idx: int, max_digits: int, 
                         is_tight: bool, limit: int, suffix: str, dp: list) -> int:
        if idx == max_digits:
            return 1
        if dp[idx][1 if is_tight else 0] != -1:
            return dp[idx][1 if is_tight else 0]
        
        suffix_len = len(suffix)
        
        if idx >= max_digits - suffix_len:
            suffix_idx = idx - (max_digits - suffix_len)
            low = high = int(suffix[suffix_idx])
        else:
            high = min(limit, int(number_str[idx])) if is_tight else limit
            low = 0
        
        total = 0
        for digit in range(low, high + 1):
            new_tight = is_tight and (digit == int(number_str[idx]))
            total += self.countValidNumbers(number_str, idx + 1, max_digits, new_tight, limit, suffix, dp)
        
        dp[idx][1 if is_tight else 0] = total
        return total

    def solveUpTo(self, num_str: str, num_digits: int, limit: int, suffix: str) -> int:
        dp = [[-1] * 2 for _ in range(self.MAX_DIGITS)]
        result = self.countValidNumbers(num_str, 0, num_digits, True, limit, suffix, dp)
        if self.checkSubtract(num_str, num_digits, suffix, limit):
            result -= 1
        return result

    def numberOfPowerfulInt(self, start: int, finish: int, limit: int, suffix: str) -> int:
        suffix_val = int(suffix)
        finish_str = str(finish)
        start_str = str(start - 1)
        
        finish_digits = len(finish_str)
        start_digits = len(start_str)
        
        upto_finish = self.solveUpTo(finish_str, finish_digits, limit, suffix) if finish >= suffix_val else 0
        upto_start = self.solveUpTo(start_str, start_digits, limit, suffix) if suffix_val < start else 0
        
        return upto_finish - upto_start
*/