The Wraith-Peal of Gallowmoor Belfry
High on the moor stands the Gallowmoor Belfry, and the wardens of the Ashen Rope keep its bells. Each bell is marked with a single letter. A night's ringing is written down as the peal: the letters of the bells struck, in the order they were struck.
A wraith that haunts the belfry can be bound by its true name, the word. It is bound once for every distinct way the word can be picked out of the peal: choose one strike for each letter of the word, so that the chosen strikes spell the word from first letter to last and occur in the peal in that same order. The wardens pay by the binding, so they need the exact count.
Write countBindings(peal, word).
pealis a string of lowercase lettersa–z. It may be empty.wordis a string of lowercase lettersa–z. It may be empty.
Return the number of index sequences i1 < i2 < ... < ik (where k is the length of word) such that the letter of peal at position i1 is the first letter of word, the letter at i2 is the second, and so on. Two ways are different if they use different sets of positions. If word is empty, there is exactly one way (choose nothing). If no way exists, return 0.
The count can be very large, so return it modulo 1,000,000,007 as an integer.
examples
- case 1
peal "bellbell", word "bel"8 — the first b with the first e can take any of four l's; the first b with the second e, two; the second b with the second e, two - case 2
peal "aaaa", word "aa"6 — any two of the four strikes, taken in order - case 3
peal "ab", word ""1 — the empty name is bound by choosing no strikes at all - case 4
peal "ab", word "abc"0 — the name is longer than the peal
- reward
- 320 XP
- signature
countBindings
TypeScript, run as ES2022 — types are stripped, not checked. If a JS engine would run it, so will we.
- bellbell spells bel eight ways
- repeated letters choose pairs
- empty word is bound once
- empty peal binds nothing
- both empty
- word longer than peal
- babgbag spells bag
- rabbbit spells rabbit
- dingdongding spells dig
- ten choose five
- letters absent from peal
- forty choose twenty wraps the modulus