A music box plays the tune tune, one lowercase letter per note. By muting any set of notes you hear a melody: the notes that remain, in their original order. A melody must be non-empty, and a pleasant melody never plays the same note twice in a row.
Return how many different pleasant melodies can be heard, modulo 10**9 + 7. Two melodies are the same when they are the same string, however the muted notes were chosen.
Examples
Input: tune = "aba"
Output: 5
Explanation: "a", "b", "ab", "ba", "aba" ("aa" repeats a note).
Input: tune = "aab"
Output: 3
Explanation: "a", "b", "ab".
Input: tune = "aaaa"
Output: 1
Constraints
0 <= len(tune) <= 10**5, lowercase letters only- Target complexity: O(n) (times the alphabet size at most). Collecting melodies in a set is exponential.
Goals
- Count distinct subsequences without listing them
- Index the dp by the last letter instead of by position to avoid double counting
- See why a later occurrence of a letter replaces, rather than adds to, the earlier count