1213. Distinct Mirror Pieces
A word-game designer wants to know how many different mirror words hide inside a puzzle string. Given a lowercase string s, count the distinct non-empty substrings that read the same forwards and backwards. Two substrings are the same word when their text is equal, no matter where they occur, so in aaa the pieces a, aa and aaa give 3 distinct words even though a appears three times.
Return that number as an int. A string of length n has at most n distinct palindromic substrings, so a palindromic tree, or Manacher's radii plus hashing, solves it in about O(n) time and O(n) space. Listing every substring is far too slow for the longest inputs.
Example 1
- Input:
- s = "abaab"
- Output:
- 5
- Explanation:
The distinct palindromes are
a,b,aba,aaandbaab, so the answer is 5.
Example 2
- Input:
- s = "aaa"
- Output:
- 3
- Explanation:
The distinct palindromes are
a,aaandaaa, so the answer is 3.
Example 3
- Input:
- s = "abc"
- Output:
- 3
- Explanation:
Only the three single letters are palindromes, so the answer is 3.
Constraints
1 ≤ s.length ≤ 105
s contains only lowercase letters
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 4,000 msC++ 1,000 msJava 2,000 msJavaScript 2,000 msTypeScript 2,000 ms
Expected complexity
- Time
- O(n)
- Space
- O(n)