Palindromic Substrings

Problem

Given a string, return the count of substrings (contiguous, distinct positions) that are palindromes.

Constraints

• 1 ≤ s.length ≤ 1000

Approach — Two Pointers

This is a Two Pointers problem. The idea: walk two indices through the data together (or toward each other), turning an O(n²) pair search into one linear pass. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: O(n) time, O(1) extra space.

Solution code

Python

class Solution:
    def countSubstrings(self, s):
        n = len(s)
        count = 0
        for c in range(n):
            for lo, hi in ((c, c), (c, c + 1)):
                while lo >= 0 and hi < n and s[lo] == s[hi]:
                    count += 1
                    lo -= 1
                    hi += 1
        return count

Java

class Solution {
    public int countSubstrings(String s) {
        int count = 0;
        for (int i = 0; i < s.length(); i++) {
            count += expand(s, i, i);
            count += expand(s, i, i + 1);
        }
        return count;
    }
    private int expand(String s, int l, int r) {
        int c = 0;
        while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
            c++; l--; r++;
        }
        return c;
    }
}

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.