831. Distinct Mirror Subsequences
A mirror word reads the same from both ends. Given a string s made only of the letters a, b, c and d, count how many different non-empty mirror words can be formed as subsequences of s (letters kept in order, not necessarily adjacent).
Two subsequences are the same when they spell the same text, even if they use different positions of s. Since the count can be large, return it modulo 1000000007. Aim for time O(n^2) and space O(n^2).
Example 1
- Input:
- s = "badcab"
- Output:
- 14
- Explanation:
The distinct palindromic subsequences are counted by value, not by position; here there are
14of them.
Example 2
- Input:
- s = "cc"
- Output:
- 2
- Explanation:
Only
candccqualify, even though the single letter appears at two positions:2.
Example 3
- Input:
- s = "abdbad"
- Output:
- 13
- Explanation:
Several index choices give the same text and count once, leaving
13different palindromes.
Constraints
1 ≤ s.length ≤ 400
s consists only of the characters a, b, c and d.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n^2)
- Space
- O(n^2)