Palindromic Substrings - Video Solutions

Problem Overview: You are given a string s. The task is to count how many substrings of s are palindromes. A substring is valid if it reads the same forward and backward. Single characters count as palindromes, so every index contributes at least one result.

Approach 1: Brute Force Check (O(n^3) time, O(1) space)

The most direct idea is to generate every possible substring and check whether it is a palindrome. Two nested loops choose the start and end indices, producing O(n^2) substrings. For each substring, run a palindrome check using two pointers from both ends toward the center. That check costs O(n) in the worst case, giving an overall complexity of O(n^3). This approach demonstrates the problem definition clearly but becomes too slow for large inputs.

Approach 2: Expand Around Center (O(n^2) time, O(1) space)

A palindrome mirrors around its center. Every palindrome can be expanded from either a single character (odd length) or the gap between two characters (even length). Iterate through the string and treat each index as a potential center. From each center, expand two pointers outward while the characters match. Each successful expansion forms a valid palindromic substring and increments the count. There are 2n - 1 possible centers, and each expansion may scan outward up to O(n), giving O(n^2) time overall with constant extra memory. This technique relies on simple pointer movement and is closely related to Two Pointers and String processing patterns.

Approach 3: Dynamic Programming (O(n^2) time, O(n^2) space)

Dynamic programming stores whether each substring s[i..j] is a palindrome. Define a DP table where dp[i][j] is true if the substring from index i to j is a palindrome. Single characters are always palindromes, and two characters are palindromes if both characters match. For longer substrings, the condition becomes s[i] == s[j] && dp[i+1][j-1]. Iterate over substring lengths from small to large and update the table while counting valid palindromes. The algorithm runs in O(n^2) time but uses O(n^2) memory to store the table. This method is useful for understanding palindrome substructure and practicing Dynamic Programming.

Recommended for interviews: Expand Around Center is the expected solution. It achieves optimal O(n^2) time while using O(1) space and requires only simple pointer logic. Starting with brute force shows you understand the problem, but quickly shifting to center expansion demonstrates strong problem-solving instincts and familiarity with common string patterns.