DSA sheet · Strings · Two Pointers pattern

Longest Palindromic Substring

In this video the teacher takes a string and finds its longest piece that reads the same from both ends. She first builds the obvious brute force (make every substring, check each one with two pointers), works out why it is about n³, and then flips the palindrome check around: instead of starting at the two ends and shrinking inwards, she starts in the middle and expands outwards. That one change removes a whole loop and gives O(n²). She also explains why two pointers is the right pattern here (and not sliding window), how to handle odd and even palindromes, and how to get the substring back when you only have one index and a length. The same trick is reused in the very next problem (Palindromic Substrings), so it's worth learning well.

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: every substring + a two-pointer check
• Part B · Optimal: expand around every center
• Part C · Revision page

Part 0 · Before starting

Words used on this page

• Index: the position of a character, counted from 0. In "babad", index 0 is b, index 4 is d.
• Substring: a continuous piece of the string. You can't jump over characters. In "babad", "aba" (indexes 1..3) is a substring, but "bbd" is not, because it skips the letters in between.
• Palindrome: a string that reads the same forwards and backwards, like "bab", "abba" or "racecar". Every single letter is a palindrome on its own.
• Pointer: just an integer variable holding an index. "Moving a pointer" means adding or subtracting 1.

What "two pointers" means

The slow way to look at pairs of positions is two nested loops: try every (i, j). That's about n·n/2 pairs, so O(n²). Two pointers is the idea of keeping just two indexes and moving them by a rule, so that at each step you can safely throw away some pairs without checking them. Usually this works because the array is sorted, or has some shape, that tells you which pointer to move. The teacher's point in this batch: sorting is not the real requirement. What you really need is to know which pointer to move, and when.

The family of patterns in this playlist, in one line each:

This page needs the last two rows. Here they are properly.

Checking a palindrome: reverse copy vs two pointers

The teacher recalls the two ways she taught earlier for checking whether something like "bab" is a palindrome:

1. Reverse copy: make a second string that is the first one reversed, then compare them letter by letter. It works, but it needs extra space to hold the reversed copy.
2. Two pointers (better): reading the same from both sides means the 1st letter equals the last, the 2nd equals the 2nd-last, and so on. So put left = 0, right = n − 1. If s[left] != s[right], it's not a palindrome, stop right away. If they match, move both inwards (left += 1, right -= 1) and compare the next pair. No extra space.

How many comparisons? The pointers meet in the middle, so a string of length n needs only about n/2 comparisons. Length 3 → 1 comparison. Length 5 → 2 comparisons (the middle letter is never compared). The loop runs while left < right: when they point to the same index there's nothing to compare, and once they cross, every pair is done.

Expand around a center (the idea used in Part B)

Every palindrome is symmetric around its middle. So instead of starting at the two ends and moving in, you can start at the middle and move out: if the letters just left and just right of the current palindrome are equal, the bigger piece is also a palindrome. Keep going until they differ or you fall off the string.

But where is "the middle"? It depends on the length:

• Odd length (like "bab", "racecar"): the middle is one letter. Start with left = right = i.
• Even length (like "bb", "abba"): there is no middle letter. The middle is the gap between two letters. Start with left = i, right = i + 1.

Why are there 2n − 1 centers? A string of n letters has n letters and n − 1 gaps between neighbouring letters. Each palindrome has exactly one center, and it's either a letter (odd) or a gap (even). So the possible centers are n + (n − 1) = 2n − 1. For "babad" (n = 5) that's 5 letter-centers + 4 gap-centers = 9:

  letters:   b     a     b     a     d
  index:     0     1     2     3     4
  centers:   o  e  o  e  o  e  o  e  o
             ↑  ↑
   o = odd center (a letter, L = R = i)
   e = even center (the gap between i and i+1, L = i, R = i+1)

   5 odd + 4 even = 9 = 2·5 − 1 centers

In code we loop i from 0 to n−1 and try both kinds at every i. At the last i, the "even" call uses i+1 = n, which is outside the string, so it stops at once and finds nothing. That's why we make 2n calls but only 2n − 1 real centers.

Part A · Brute force: every substring + a two-pointer check

LeetCode 5

1The question in simple words

You get a string s. Return the longest substring of s that is a palindrome. You return the substring itself, not its length.

The teacher lists everything for s = "babad", length by length:

The longest is length 3, and there are two of them: "bab" and "aba". The question doesn't say which one to pick, so either is accepted. Returning whichever you find first is fine.

Example 2: s = "cbbd" → answer "bb" (an even-length palindrome, which will matter in Part B).

2What the constraints tell us

• 1 ≤ s.length ≤ 1000, so n ≤ 10³. The string is never empty, so there is always an answer of at least length 1.
• She reads this first because it tells us which complexity will pass. With n = 10³: n² = 10⁶ (easy), n³ = 10⁹ (too much). The usual budget is about 10⁸ simple operations; beyond that you risk TLE (Time Limit Exceeded).
• The characters are digits and English letters, which doesn't change the method.

3Intuition: try every substring, keep the longest palindrome

The simplest plan has two jobs:

1. Make every substring (two loops: a start i and an end j).
2. Check each one with the two-pointer palindrome check from Part 0. If it's a palindrome and longer than the best one found so far, remember it.

Making every substring with i and j

This is the same way we listed all subarrays in the arrays topic. Fix the start i, then let the end j walk from i to the end of the string:

4Building the logic from the example

Don't build the substring for the check, pass i and j

The check function doesn't need a new string. Give it the whole s plus the two ends i and j, and it uses them directly as left and right. It only compares letters between those two positions.

Is it the longest so far? Use the length j − i + 1

Being a palindrome isn't enough. We want the longest. So we keep the best answer in res (it starts as the empty string, length 0), and when we find a palindrome from i to j, we compare its length with len(res).

The length of the piece from i to j, with both ends included, is j − i + 1. For i = 0, j = 2 ("bab") that's 2 − 0 + 1 = 3.

Cutting out the answer: why j + 1?

Slicing (Java's substring(i, j), Python's s[i:j]) includes the start and excludes the end. We want index j included, so we cut s[i:j + 1]. For i = 0, j = 0 that's s[0:1] = "b", exactly one letter, which is what we want.

Watching it on "babad"

• i = 0, j = 0: "b" is a palindrome, length 1 > 0 → res = "b".
• i = 0, j = 1: "ba", b ≠ a → not a palindrome, skip.
• i = 0, j = 2: "bab" ✓, length 3 > len("b") = 1 → res = s[0:3] = "bab".
• Later, "aba" (i = 1, j = 3) is also a palindrome of length 3, but 3 is not greater than 3, so res stays "bab". That's why the brute force returns the first longest one it finds.

5Approach steps

1. res = "".
2. For every start i from 0 to n−1, and every end j from i to n−1:
3. Check whether s[i..j] is a palindrome with two pointers moving inwards (left = i, right = j).
4. If it is, and j − i + 1 > len(res), set res = s[i:j+1].
5. After both loops, return res.

6Code (Python)

class Solution:
    def longestPalindrome(self, s):
        res = ""
        n = len(s)
        for i in range(n):                    # i = start of the substring
            for j in range(i, n):             # j = end, begins at i
                if self.isPalindrome(s, i, j):
                    if j - i + 1 > len(res):  # longer than the best so far?
                        res = s[i:j + 1]      # j + 1 because the end is excluded
        return res

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

7Code line by line

8Dry run (hand table)

s = "babad". "pairs compared" lists the (left, right) comparisons that isPalindrome makes.

The key moment, i = 0, j = 2 (the check works inwards from both ends):

Final answer: "bab" ✓ (15 substrings checked, which is n(n+1)/2 for n = 5).

9Complexity & remember

• Time O(n³): two nested loops make about n² substrings, and each check costs up to about n/2. The teacher's count for n = 1000: 10³ · 10³ · 500 = 5 × 10⁸ operations. That's above the 10⁸ comfort line, so it may TLE. In her run it was accepted, because each step is a very simple character comparison, but it was very slow.
• Space O(1) extra for the check (we pass indexes). Only res holds a copy of the best answer.
• What can we improve? The palindrome check itself is already as cheap as it can be (n/2). So the waste must be in the two loops that make the substrings. Part B removes one of them.

Part B · Optimal: expand around every center

1The question again, with the new goal

Same input and output: return the longest palindromic substring of s. The goal now is to stop generating substrings with two loops and get from about n³ to about n².

2What the constraints tell us

• n ≤ 1000 → n² = 10⁶. That is far below 10⁸, so an O(n²) solution is comfortable. We don't need anything cleverer for this problem.
• n ≥ 1 → at least one letter, so the answer has length at least 1.

3Intuition: check the palindrome from the inside out

In Part A, to check "bab" we start at the two ends and shrink. The teacher's trick is to do the opposite: start at the middle and expand.

• Put left and right on the middle letter of "bab" (index 1).
• Then left -= 1, right += 1 and compare. If they match (b and b), the bigger piece is a palindrome too. If the string were "cbabc", we'd step out again and compare c with c, and so on.
• Stop as soon as they differ or a pointer falls off the string.

The win: for each center, one expansion finds the longest palindrome around it, and along the way it has passed through every smaller one around it too. So instead of handing the function a substring (two indexes from two loops), we hand it only the index i and tell it to grow by itself. One loop over the centers replaces the two loops over (i, j).

4Building the logic from examples

Odd and even centers

The teacher points out a catch. For an odd palindrome like "bab", left and right start on the same letter. But for an even palindrome like "aa" or "abba", there is no middle letter, so they must start on two neighbouring letters: left = i, right = i + 1. Then expand the same way. Using "aaaa" as the example: put L at index 1 and R at index 2, they match; step out to 0 and 3, they match, so "aaaa" is a palindrome.

We don't know in advance whether index i is the middle of an odd palindrome, an even one, or both. So for every i we try both: expand(s, i, i) and expand(s, i, i + 1), and keep the longer result. Over all i this covers all 2n − 1 centers from Part 0.

The while condition: three checks, and their order

While building it, the teacher first carried over the shrinking loop's left < right condition, then realised expanding needs something different. When we expand, left goes down and right goes up, so they can run off the ends: left can become −1 and right can become n. So the loop needs:

1. left >= 0: left is still inside the string.
2. right < len(s): right is still inside the string.
3. s[left] == s[right]: the two letters match.

The two boundary checks must come first. and stops at the first False, so we only read s[left] and s[right] when both are valid indexes.

Return a length instead of True

Part A's check returned True or False, and we had i and j to work out the length. Now the function only got one index, so True alone wouldn't tell us how long the palindrome is. So the teacher changes the return value: return the length of the palindrome it grew.

When the loop stops, left and right have gone one step too far. They point at the first bad pair (or outside the string). The palindrome is the part strictly between them. Her example: s = "babad", odd center at i = 0:

• Start L = R = 0: b = b ✓ → L = −1, R = 1.
• L = −1 is outside → stop. The real palindrome is just "b", length 1.
• The usual formula right − left + 1 gives 1 − (−1) + 1 = 3, wrong. right − left gives 2, still wrong. right − left − 1 gives 1, right.

Why minus 1? The palindrome runs from left + 1 to right − 1. Its length is (right − 1) − (left + 1) + 1 = right − left − 1. Her advice: don't memorise formulas. Work them out from where your code leaves the pointers. Here they finish on invalid positions, so the "+1" formula doesn't apply.

Check it on an even center that finds nothing: i = 0, L = 0, R = 1, b ≠ a, so the loop never runs → 1 − 0 − 1 = 0. Correct: no even palindrome there.

Getting the substring back from i and a length

In Part A we had both ends (i and j), so we could cut s[i:j+1]. Now we only have the center i and the length. The palindrome reaches about half its length to the left of i and half to the right. Her example: "bab" in "babad", center i = 1, length 3. Going 1 step left gives index 0, going 1 step right gives index 2, so "bab" is s[0..2].

The exact formulas, which handle odd and even:

Only update when it's longer

We can't overwrite start/end at every i, or a short palindrome found later would replace a longer one found earlier. So first compare. end − start is the "j − i" of the best piece so far, and we update when length > end − start.

Why save indexes and not the string?

We could keep a res string and cut a new copy every time we find a better palindrome. The teacher instead keeps only the two numbers start and end, and cuts the substring once, at the very end. That avoids making copies inside the loop. start = end = 0 at the beginning means "the first letter", which is always a valid palindrome of length 1.

5Approach steps

1. start = end = 0.
2. For every index i:
3. len1 = expand(s, i, i) (odd, the center is the letter i).
4. len2 = expand(s, i, i + 1) (even, the center is the gap after i).
5. length = max(len1, len2).
6. If length > end − start: start = i − (length − 1)//2, end = i + length//2.
7. expand: while inside the string and s[left] == s[right], move left down and right up. Return right − left − 1.
8. Return s[start:end + 1].

6Code (Python)

class Solution:
    def longestPalindrome(self, s):
        start, end = 0, 0                     # best palindrome = s[start..end]
        for i in range(len(s)):
            len1 = self.expand(s, i, i)       # odd: center is the letter i
            len2 = self.expand(s, i, i + 1)   # even: center is the gap after i
            length = max(len1, len2)
            if length > end - start:
                start = i - (length - 1) // 2
                end = i + length // 2
        return s[start:end + 1]               # cut the string only once

    def expand(self, s, left, right):
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1                         # grow outwards
            right += 1
        return right - left - 1               # both pointers went one step too far

7Code line by line

8Dry run

s = "babad". Each row is one call of expand. "grows" lists the pairs it compared.

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

How far each of the 9 centers grows (the picture to keep in your head):

  index:      0   1   2   3   4
  s:          b   a   b   a   d

  odd  @0     b                          → 1
  even @0|1   ✗                          → 0
  odd  @1    [b   a   b]                 → 3   "bab"
  even @1|2       ✗                      → 0
  odd  @2        [a   b   a]             → 3   "aba"
  even @2|3           ✗                  → 0
  odd  @3                 a              → 1   (b ≠ d stops it)
  even @3|4               ✗              → 0
  odd  @4                     d          → 1

Final answer: "aba" ✓, a valid longest palindrome (length 3). As explained in the tie doubt, the brute force gave "bab". Both are accepted.

Second check, s = "cbbd": at i = 1 the even center (1, 2) b = b ✓ grows to (0, 3) c ≠ d ✗ → length 3 − 0 − 1 = 2 → start = 1 − 0 = 1, end = 1 + 1 = 2 → "bb" ✓.

9Complexity & remember

• Time O(n²): one loop over the n positions (2n − 1 centers). Each expansion can grow at most about n/2 steps, the same cost as the shrinking check in Part A, just in the other direction. So n · n/2 → O(n²). We saved a whole factor of n by not generating substrings.
• Space O(1): a few integers. The answer is cut only once at the end.
• On LeetCode it ran much faster than the brute force.
• Can it be even faster? Yes. Manacher's algorithm solves this in O(n). The teacher calls it advanced and leaves it for a separate video. For interviews, expand-around-center is the expected answer.

Part C · Revision page

s = Solution()
print(s.longestPalindrome("babad"))              # "bab" or "aba"
print(s.longestPalindrome("cbbd"))               # "bb"   (even center)
print(s.longestPalindrome("a"))                  # "a"
print(s.longestPalindrome("ac"))                 # "a"    (any single letter)
print(s.longestPalindrome("aaaa"))               # "aaaa" (all the same letter)
print(s.longestPalindrome("forgeeksskeegfor"))   # "geeksskeeg"

Based on this video: Longest Palindromic Substring | Two Pointers