Mirror Substring Count
Medium1-D Dynamic Programming
Problem
A mirror substring reads the same forwards and backwards. Given a lowercase string s, count how many of its substrings are mirror substrings.
Substrings at different positions count separately, even if they contain the same letters.
Example 1
- Input:
- s = "abba"
- Output:
- 6
"a", "b", "b", "a", "bb" and "abba".
Example 2
- Input:
- s = "aaaa"
- Output:
- 10
Every one of the 4 + 3 + 2 + 1 substrings is a mirror.
Constraints
- 1 ≤ s.length ≤ 1000
- s contains lowercase English letters.
Hint
Show the first hint
s[i..j] is a mirror exactly when s[i] == s[j] and the inside s[i+1..j-1] is a mirror (or too short to matter).
Walkthrough
How to approach it
01Clarify before coding
- Do single characters count? Yes, every one-letter substring is a mirror.
- Are equal substrings at different positions counted twice? Yes, count by position.
- Is the answer large? At most n(n+1)/2 = 500,500, so no modulo needed.
02Brute force
Enumerate all O(n²) substrings and check each by reversing it.
Cost: O(n³): about 1.7·10^8 character comparisons for n = 1000.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.