High-Concurrency Prompt Template Deduplication (Array + Hash Map)

Problem: High-Concurrency Prompt Template Dedup & Counting (Array + Hash Map) You run a prompt engineering service receiving many prompt template strings. To reduce caching/eval cost, you need to normalize templates and count duplicates. Given an array templates of length n, return a mapping from each normalized key to its frequency. Normalization rules For each template: Collapse all consecutive whitespace (space/tab/newline) into a single space. Trim leading/trailing spaces. Replace placeholders of the form {variable} with {}, where variable consists of letters/digits/underscore. Keep all other characters unchanged (case-sensitive). Output Return count_by_key: key: normalized template string value: number of occurrences Constraints & requirements 1 <= n <= 2e5 Each template length <= 2e4, total length <= 2e6 Target time: O(total_length) Explain the data structure/complexity and discuss thread-safety strategies under high concurrency (sharded maps, lock granularity, queues, etc.). Example Input: [ "Summarize {doc_id} in {lang}", "Summarize {x} in {y}", "Summarize\n{doc_id}\tin\t{lang} ", "Translate {text} to {lang}" ] Output: { "Summarize {} in {}": 3, "Translate {} to {}": 1 } Example Input 4 Summarize {doc_id} in {lang} Summarize {x} in {y} Summarize {doc_id} in {lang} Translate {text} to {lang} Output {"Summarize {} in {}": 3, "Translate {} to {}": 1}