Zero-Filtered Digit Products for Substring Queries

### Problem You are given a decimal digit string `s` and an array of inclusive, zero-based queries `[l,r]`. For each query, consider `s[l..r]`. Remove all zero digits while retaining every other digit in its original order, and interpret the result as an integer `x`. If no nonzero digit remains, use `x=0`. Multiply `x` by the sum of its digits. Return the query results in their original order, each reduced modulo `1000000007`. ```cpp class Solution { public: vector<int> sumAndMultiply(string s, vector<vector<int>>& queries); }; ``` ### Examples **Example 1:** ```text Input: s = "506070", queries = [[0,5],[1,4],[3,3]] Output: [10206,871,0] Explanation: The retained numbers are 567,67,0, with digit sums 18,13,0. Their products are 10206,871,0. ``` **Example 2:** ```text Input: s = "00909", queries = [[0,1],[2,4],[4,4]] Output: [0,1782,81] Explanation: "00" retains no digits. "909" retains 99, whose digit sum is 18. The final one-character query retains 9, giving 9*9 = 81. ``` ### Constraints - `1 <= s.length <= 100000`. - `s` contains only decimal digits. - `1 <= queries.length <= 100000`. - Every query has exactly two entries `[l,r]` with `0 <= l <= r < s.length`. ### Clarifying Questions - May `s` or a queried substring begin with zeros? Yes. - Are both query endpoints included? Yes. - May retained digits be reordered or deduplicated? No. - Is the digit sum taken before or after modular reduction of `x`? It is the sum of the actual retained digits; reduce the final product as specified. - Should outputs follow query order? Yes, even when queries overlap or repeat. ### What a Strong Answer Covers - Exact substring boundaries, retained digit order, and the correct digit sum. - Modular results without assuming the retained integer fits a built-in type. - All-zero ranges, single-character ranges, leading zeros, and overlapping queries. - A correctness proof and time and memory bounds for both maximum lengths. ### Follow-up Questions - How would returning the retained digit strings affect total output size? - What changes in the specification if the underlying string can be edited between queries? ```hint Preserve lengths as well as modular values Maintain original-position prefix counts of nonzero digits, their modular concatenation values, and digit sums. The count difference gives the number of retained digits in a query. Powers of ten then let you remove the earlier concatenated prefix, while digit-sum differences provide the multiplier. ```