Charm Bracelet Cuts
Medium · dynamic programming
A bead maker has a long string of beads, written as the lowercase letters in beads, one letter per bead. She wants to cut the string into charms, keeping the beads in their original order and using every bead exactly once.
A block of consecutive beads can be a charm only if it is one of these:
- a single bead;
- a block where every bead has the same letter, such as
kkk; - a block where each bead is the next letter of the alphabet after the one before it, such as
cde. There is no wrap-around:zis never followed bya.
Two ways of cutting are different if they cut the string at different places. Return the number of ways to cut the whole string into charms, modulo 10^9 + 7.
Examples
Example 1
Input: beads = "aab"
Output: 3
The ways are a|a|b, aa|b and a|ab. The block aab is not a charm.
Example 2
Input: beads = "zyx"
Output: 1
Going down the alphabet never makes a charm, so every bead stands alone.
Example 3
Input: beads = "abcc"
Output: 6
Either the last c is its own charm (4 ways to cut abc: a|b|c, ab|c, a|bc, abc) or it joins the c before it as cc (2 ways to cut ab: a|b, ab).
Constraints
- 1 <= len(beads) <= 10^5
- beads contains only lowercase English letters