Mirrored Reaction Badges
Count distinct nonempty palindromic subsequences of a string by length parity
A social network records the reaction types on a post as a string reactions. Each lowercase letter identifies one reaction type.
The network can create a badge by keeping a nonempty subsequence of this string: it may delete any positions, but the remaining letters must stay in their original order. A badge is eligible only if its string is a palindrome, meaning it reads the same forward and backward.
Badges are identified by their resulting strings, not by the positions used to create them. If several choices of positions produce the same string, that badge is counted only once.
Return a two-element list [odd, even], where:
oddis the number of distinct eligible badge strings with odd length.evenis the number of distinct eligible badge strings with even length.
Return each count modulo 1,000,000,007. The empty string is not a badge. If reactions is empty, return [0, 0].
Examples
Example 1
Input: reactions = "abca" Output: [5,1]
For `abca`, the distinct odd-length badges are `a`, `b`, `c`, `aba`, and `aca`. The only even-length badge is `aa`. Different occurrences of `a` do not create different one-letter badges.
Example 2
Input: reactions = "aaaa" Output: [2,2]
For `aaaa`, each possible nonempty length produces exactly one distinct badge string. Their lengths determine which of the two counts they contribute to.
Example 3
Input: reactions = "" Output: [0,0]
An empty reaction history cannot produce a nonempty badge.
Constraints
- 0 <= reactions.length <= 800
- reactions contains only lowercase English letters.
The intended solution uses O(n^2) time and O(n^2) space. Modular subtraction must be normalized to a nonnegative residue.
Hints
Show hint 1Hint 1
For each interval, track two counts: distinct odd-length palindromes and distinct even-length palindromes. Unequal endpoints allow an inclusion-exclusion transition.
Show hint 2Hint 2
When the endpoints match, wrapping interior palindromes creates new candidates. To remove duplicates, locate the first and last occurrences of that same letter strictly inside the interval, distinguishing zero, one, and multiple interior occurrences.
Follow-up questions
What an interviewer might ask once you have a working solution.
- How would you change the states and transitions to classify badge lengths modulo three instead of modulo two?
- How would the recurrence change if different choices of source positions were counted as different badges?
Practice this with an AI interviewer
Explain your approach out loud, write Python or JavaScript, run it against hidden tests (including large inputs), and get a scored debrief.
Start this problem