Count number of different characters for every substring in a string w/ another string

Revision en2, by Qualified, 2020-11-12 01:32:07

The title prolly ain't clear at all. You are given a string $$$s$$$ and a string $$$t$$$. For every substring $$$s$$$ of length $$$|t|$$$, you are to find the number of different characters between the substring of $$$s$$$ and $$$t$$$ in $$$O(n)$$$ or less. It is guaranteed that $$$|t| \le |s|$$$.

Example: s: abac t: ag output: [1, 2, 1]

s: adfjaasd t: asdf output: [3, 4, 4, 4, 4]

Tags #strings

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en6 English Qualified 2020-11-12 21:33:28 2 Tiny change: ' 4, 4, 4, 4]\n\nDon't' -> ' 4, 4, 4, 3]\n\nDon't'
en5 English Qualified 2020-11-12 17:22:19 13 Tiny change: 't$ in $O(n)$ or less' -> 't$ in $O(nlog(n))$ or less'
en4 English Qualified 2020-11-12 16:22:39 39 Tiny change: 'low (-75).' -> 'low (-75).\n\nProblem statement: [problem:1196D2]'
en3 English Qualified 2020-11-12 05:16:58 140
en2 English Qualified 2020-11-12 01:32:07 18 Tiny change: 's$ and $t$. It is gu' -> 's$ and $t$ in $O(n)$ or less. It is gu'
en1 English Qualified 2020-11-12 01:31:11 430 Initial revision (published)