Letter Frequency in Substrings

Given a lowercase string s and queries [l, r, ch], return for each query how many times the letter ch occurs in s[l..r] inclusive.

Examples

Input:  s = "mississippi", queries = [[0, 3, "s"], [4, 10, "i"], [0, 10, "p"], [2, 2, "m"]]
Output: [2, 3, 2, 0]
Explanation: "miss" holds two s; "issippi" holds three i; the whole word holds two p; s[2] is not m.

Input:  s = "a", queries = [[0, 0, "b"]]
Output: [0]

Constraints

• 1 <= len(s) <= 2 * 10**4, 0 <= len(queries) <= 10**5
• 0 <= l <= r < len(s), ch is a single lowercase letter
• Target complexity: O(26 * n + q). Counting inside each substring separately is too slow for the largest tests.

Goals

• Keep one prefix-count array per distinct letter
• Build prefix tables lazily so unused letters cost nothing