Count Mirror Substrings

MediumTries & Strings

Problem

Given a string s, count how many of its substrings are palindromes. Substrings at different positions count separately even when their text is the same.

Example 1

Input:
s = "aaa"
Output:
6

Three "a", two "aa" and one "aaa".

Example 2

Input:
s = "abc"
Output:
3

Example 3

Input:
s = "abba"
Output:
6

a, b, b, a, "bb" and "abba".

Constraints

  • 1 ≤ s.length ≤ 2000
  • s consists of lowercase English letters.

Hint

Show the first hint

Checking each of the ~n²/2 substrings separately repeats work.

Walkthrough

How to approach it

01Clarify before coding

  • Do equal substrings at different positions count twice? Yes.
  • Do single characters count? Yes, each is a palindrome.
  • How big can the answer be? Up to n(n + 1)/2 ≈ 2·10^6, which fits in an int.

02Brute force

Enumerate all substrings and check each with two pointers.

Cost: O(n³): about 2.7·10^9 character checks for n = 2000.

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.

Solve it in the browserStart free

This problem is part of Pro.