DSA sheet · Strings · Two Pointers pattern

Palindromic Substrings

This is the last question of the two-pointers strings section. It's a close cousin of Longest Palindromic Substring (Problem 9): there we wanted the longest palindrome, here we count all of them. The teacher reuses the same two steps: a brute force that makes every substring and checks it with two pointers (about n³), then expand around center, where every successful step outwards is one more palindrome to count (n²). She also clears up a common confusion: two pointers is not only for sorted arrays. You can use it whenever you know which pointer to move and when.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · Two pointers from scratch (what this page needs)
• Part A · Brute force: count every substring that passes the check
• Part B · Optimal: expand around every center and count each step
• Part C · Revision page

Part 0 · Before starting

Words used on this page

• Index: the position of a character, counted from 0.
• Substring: a continuous piece of the string, with no characters skipped. The same letters at different positions count as different substrings. In "aaa", index 0 alone and index 1 alone are two separate substrings, even though both are "a".
• Palindrome: reads the same forwards and backwards ("a", "aa", "aba", "abba"). Every single letter is one.
• Pointer: an integer variable that holds an index.

What "two pointers" means

Looking at every pair of positions with two nested loops costs about n²/2 pairs, so O(n²). With two pointers you keep just two indexes and move them by a rule, so some pairs are skipped safely. People often say "two pointers needs a sorted array". The teacher corrects this: sorting is just the usual reason we know which pointer to move. If the problem gives you that knowledge some other way (like matching letters in a palindrome), two pointers works on unsorted data too.

Checking one palindrome with two pointers (shrinking)

Reading the same both ways means 1st letter = last, 2nd = 2nd-last, and so on. So set left at the start and right at the end. A mismatch means "not a palindrome". A match means both move one step inwards. Stop when they meet or cross. That's about n/2 comparisons, and it needs no reversed copy.

Expand around a center, and why there are 2n − 1 centers

Every palindrome mirrors around its middle. Start at the middle and step outwards. If the two new outer letters match, the bigger piece is a palindrome too. Stop at the first mismatch or at the edge of the string.

• Odd length ("a", "aba"): the middle is a letter → left = right = i.
• Even length ("aa", "abba"): the middle is the gap between two letters → left = i, right = i + 1.

n letters have n − 1 gaps between them, so there are n + (n − 1) = 2n − 1 possible centers. Every palindromic substring has exactly one center and one size. So if we visit every center and record every size it reaches, we meet each palindrome exactly once. That's what makes counting work.

  s:        a     a     a
  index:    0     1     2
  centers:  o  e  o  e  o        o = letter (odd), e = gap (even)
            3 odd + 2 even = 5 = 2·3 − 1

Part A · Brute force: count every substring that passes the check

LeetCode 647

1The question in simple words

You get a string s. Return how many of its substrings are palindromes. Substrings at different positions are counted separately, even if they have the same letters.

The teacher's example, s = "aaa":

All 6 substrings are palindromes → answer 6. Another example (LeetCode's first): "abc" → only the three single letters → answer 3.

2What the constraints tell us

• 1 ≤ s.length ≤ 1000 → n ≤ 10³, and the string is never empty (the answer is at least 1).
• She reads the constraints to see which pattern and which complexity will fit. n² = 10⁶ is easy. n³ = 10⁹ is past the usual ~10⁸ budget for simple operations, so it risks TLE.
• Only lowercase English letters.

3Intuition: it's Problem 9 with a counter instead of a "best"

In Longest Palindromic Substring we made every substring, checked it, and if it was a palindrome we asked "is it the longest so far?". Here the question after the check is simpler: if it's a palindrome, add 1. So the plan is:

1. Make every substring with a start i and an end j (j goes from i to the end).
2. Check each one with the shrinking two-pointer check.
3. Every time the check says yes, count += 1.

4Building the logic from examples

Generating the substrings of "aaa"

Fix i, then move j from i to the end: i = 0 gives "a", "aa", "aaa"; i = 1 gives "a", "aa"; i = 2 gives "a". That's 6 = n(n+1)/2 substrings.

Two ways to give the substring to the check

The teacher shows both:

1. Build it: keep a string sub for each i. Every time j moves, add s[j] to the end. Then sub is exactly s[i..j]: "a", then "aa", then "aaa". Pass sub to the check.
2. Don't build it, pass the indexes: give the check the whole string plus i and j as left and right. The check only moves inwards from those two positions, so it never looks outside s[i..j]. Her example: in "ababc", to check the middle "bab" (indexes 1..3), send left = 1, right = 3. It compares b with b, then meets in the middle, and never touches index 0 or 4.

5Approach steps

1. count = 0.
2. For every start i, for every end j from i to n−1:
3. If isPalindrome(s, i, j) (shrinking two pointers), do count += 1.
4. Return count.

6Code (Python)

class Solution:
    def countSubstrings(self, s):
        count = 0
        n = len(s)
        for i in range(n):                    # start of the substring
            for j in range(i, n):             # end, begins at i
                if self.isPalindrome(s, i, j):
                    count += 1                # one more palindrome
        return count

    def isPalindrome(self, s, left, right):
        while left < right:                   # until they meet or cross
            if s[left] != s[right]:
                return False
            left += 1                         # shrink inwards
            right -= 1
        return True

class Solution:
    def countSubstrings(self, s):
        count = 0
        for i in range(len(s)):
            sub = ""                          # fresh substring for each start
            for j in range(i, len(s)):
                sub += s[j]                   # sub is now s[i..j]
                if self.isPalindrome(sub, 0, len(sub) - 1):
                    count += 1
        return count

    def isPalindrome(self, s, left, right):
        while left < right:
            if s[left] != s[right]:
                return False
            left += 1
            right -= 1
        return True

7Code line by line

8Dry run (hand table)

s = "aaa".

And s = "abc" for contrast: (0,0) ✓ 1 · (0,1) a≠b ✗ · (0,2) a≠c ✗ · (1,1) ✓ 2 · (1,2) b≠c ✗ · (2,2) ✓ 3 → 3.

Final answer for "aaa": 6 ✓

9Complexity & remember

• Time O(n³): n² substrings from the two loops, times about n/2 for each check → about n³/2. The teacher's numbers for n = 1000: 10⁶ substrings × 500 comparisons = 5 × 10⁸.
• Is that too slow? Past 10⁸ you can get TLE, but it depends on how heavy each step is. Here each step is one character comparison, which is very light, so around 5–6 × 10⁸ can still pass. It was accepted when she submitted, but slowly. (Sometimes even 10⁷–10⁸ can TLE if each step does a lot of work, so this is a judgement call, not a rule.)
• Space O(1) for the index version. The "build sub" version also keeps an O(n) string.
• The check can't get cheaper than n/2. The part to cut is the two loops that generate substrings, exactly as in Problem 9.

Part B · Optimal: expand around every center and count each step

1The question again, with the new goal

Count the palindromic substrings again, but with one loop instead of two loops for generating substrings. The aim is O(n²).

2What the constraints tell us

• n ≤ 1000 → n² = 10⁶ operations, far below 10⁸. O(n²) is comfortable.
• n ≥ 1, so the loop always runs at least once and the answer is at least 1.

3Intuition: every step outwards finds one new palindrome

Same as Problem 9: for each index i, treat it as the middle of an odd palindrome (left = right = i) and as the left half of an even middle (left = i, right = i + 1). Then expand outwards while the letters match.

The new idea: each time the while condition passes, the piece s[left..right] is a palindrome. It's a substring we haven't counted yet, so do count += 1 inside the loop, then step outwards. The teacher says the brute force's "check by shrinking" can just as well be "check by expanding", and expanding lets one call find several palindromes at once.

4Building the logic from the example

The while condition

Expanding moves left down and right up, so they can fall off the string: left can become −1 and right can become n. So the loop keeps going only while left >= 0, right < len(s), and s[left] == s[right], with the two boundary checks first so we never read a bad index.

The teacher's walk on "aaa"

• i = 0, odd: L = R = 0, a letter matches itself → count 1 ("a" at 0). Next L = −1, outside → stop. Odd gave 1.
• i = 0, even: L = 0, R = 1, a = a → count 1 ("aa" at 0..1). Next L = −1 → stop. Even gave 1. So i = 0 adds 2.
• i = 1, odd: L = R = 1 → count ("a"). Step out: L = 0, R = 2, a = a → count ("aaa"). Step out: both outside → stop. Odd gave 2.
• i = 1, even: L = 1, R = 2, a = a → count ("aa" at 1..2). Next L = 0, R = 3, outside → stop. Even gave 1. So i = 1 adds 3.
• i = 2, odd: L = R = 2 → count ("a"). Next R = 3, outside → stop. Odd gave 1.
• i = 2, even: R = i + 1 = 3 is already outside → the loop never runs. Even gave 0. So i = 2 adds 1.

Total: 2 + 3 + 1 = 6 ✓, the same as the brute force.

5Approach steps

1. count = 0.
2. For every index i: count += expand(s, i, i) (odd) and count += expand(s, i, i + 1) (even).
3. expand(s, left, right): start a local found = 0. While inside the string and s[left] == s[right]: found += 1, then left -= 1, right += 1. Return found.
4. Return count.

6Code (Python)

class Solution:
    def countSubstrings(self, s):
        count = 0
        for i in range(len(s)):
            count += self.expand(s, i, i)       # odd: center is the letter i
            count += self.expand(s, i, i + 1)   # even: center is the gap after i
        return count

    def expand(self, s, left, right):
        found = 0
        while left >= 0 and right < len(s) and s[left] == s[right]:
            found += 1                          # s[left..right] is a palindrome
            left -= 1                           # grow outwards
            right += 1
        return found

7Code line by line

8Dry run

s = "aaa". Each row is one call of expand.

The string at the key moments (yellow = the pair being checked, grey = already counted inside):

How far each center grows, on "aaa" and on "abba" (an example with a mismatch):

  "aaa"      index: 0  1  2
  odd  @0          [a]               → 1
  even @0|1        [a  a]            → 1
  odd  @1          [a [a] a]         → 2   "a", "aaa"
  even @1|2           [a  a]         → 1
  odd  @2                [a]         → 1
  even @2|?                 ✗        → 0      total 6

  "abba"     index: 0  1  2  3
  odd  @0          [a]               → 1
  even @0|1         ✗  (a≠b)         → 0
  odd  @1          a [b] b  → a≠b    → 1
  even @1|2        [a [b  b] a]      → 2   "bb", "abba"
  odd  @2          a  b [b] a → b≠a  → 1
  even @2|3               ✗ (b≠a)    → 0
  odd  @3                   [a]      → 1      total 6

Final answers: "aaa" → 6 ✓, "abba" → 6 ✓ (a, b, b, a, bb, abba), "abc" → 3 ✓.

9Complexity & remember

• Time O(n²): one loop over n positions (2n − 1 centers), and each expansion grows at most about n/2 steps → n · n/2 → O(n²). We removed one whole loop compared to Part A.
• Space O(1): just a few counters and pointers.
• It was accepted and ran much faster than the brute force.

Part C · Revision page

s = Solution()
print(s.countSubstrings("aaa"))      # 6
print(s.countSubstrings("abc"))      # 3
print(s.countSubstrings("a"))        # 1
print(s.countSubstrings("aa"))       # 3   (needs the even center)
print(s.countSubstrings("abba"))     # 6
print(s.countSubstrings("aaaa"))     # 10  (all the same letter: 4·5/2)

Based on this video: Palindromic Substrings | Two Pointers