130. Mirror Piece Count
A mirror piece is a substring of consecutive characters that reads the same from left to right and from right to left; a single character is a mirror piece too. Given the string s, count how many mirror pieces it contains. Pieces that consist of the same characters but start at different positions are counted separately.
Return the total number of mirror pieces. For long strings the answer can be large, but it fits in a 32-bit integer under the given limits. Expanding around each of the 2n - 1 centres gives a quadratic solution; checking every substring separately is cubic and will time out.
Example 1
- Input:
- s = "abba"
- Output:
- 6
- Explanation:
The pieces are a, b, b, a, bb and abba, six in total.
Example 2
- Input:
- s = "xyz"
- Output:
- 3
- Explanation:
Only the three single characters are mirror pieces.
Constraints
1 ≤ s.length ≤ 2000
s contains only lower case English 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^2)
- Space
- O(1)