Palindromic Substrings

LeetCode 647 | Difficulty: Medium

Medium

Problem Description

Given a string s, return the number of palindromic substrings in it.

A string is a palindrome when it reads the same backward as forward.

A substring is a contiguous sequence of characters within the string.

Example 1:

Input: s = "abc"
Output: 3
Explanation: Three palindromic strings: "a", "b", "c".

Example 2:

Input: s = "aaa"
Output: 6
Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".

Constraints:

- `1 <= s.length <= 1000`

- `s` consists of lowercase English letters.

Topics: Two Pointers, String, Dynamic Programming

---

Approach

Dynamic Programming

Break the problem into overlapping subproblems. Define a state (what information do you need?), a recurrence (how does state[i] depend on smaller states?), and a base case. Consider both top-down (memoization) and bottom-up (tabulation) approaches.

When to use

Optimal substructure + overlapping subproblems (counting ways, min/max cost, feasibility).

---

Solutions

Solution 1: C# (Best: 80 ms)

Metric	Value
Runtime	80 ms
Memory	N/A
Date	2018-07-02

Solution

public class Solution {
    public int CountSubstrings(string s) {
        if(String.IsNullOrEmpty(s)) return 0;
    int counter =0;
    int i=0, j=0;
    for (int k = 0; k < s.Length; k++)
    {
        //even
        i=k;j=k;
        while(i>=0 && j<s.Length && s[i]==s[j])
        {
            counter++;
            i--;j++;
        }

        //odd
        i=k;
        j=k+1;
        
        while (i >= 0 && j < s.Length && s[i] == s[j])
        {
            counter++;
            i--; j++;
        }
    }
    return counter;
    }
}

📜 1 more C# submission(s)

Submission (2018-07-02) — 88 ms, N/A

public class Solution {
    public int CountSubstrings(string s)
{
    if(String.IsNullOrEmpty(s)) return 0;
    int counter =0;
    for (int k = 0; k < s.Length; k++)
    {
        //odd
        counter += ExpandAroundCenter(s, k, k);
        
        //even
        counter += ExpandAroundCenter(s, k, k+1);       
    }
    return counter;
}

private int ExpandAroundCenter(string s, int i, int j)
{
    int counter = 0;
    while (i >= 0 && j < s.Length && s[i] == s[j])
    {
        counter++;
        i--;
        j++;
    }
    return counter;
}
}

---

Complexity Analysis

Approach	Time	Space
Two Pointers	$O(n)$	$O(1)$
Dynamic Programming	$O(n)$	$O(n)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• Define the DP state clearly. Ask: "What is the minimum information I need to make a decision at each step?"
• Consider if you can reduce space by only keeping the last row/few values.
• LeetCode provides 3 hint(s) for this problem — try solving without them first.

💡 Hints

Hint 1: How can we reuse a previously computed palindrome to compute a larger palindrome?

Hint 2: If “aba” is a palindrome, is “xabax” a palindrome? Similarly is “xabay” a palindrome?

Hint 3: Complexity based hint: If we use brute force and check whether for every start and end position a substring is a palindrome we have O(n^2) start - end pairs and O(n) palindromic checks. Can we reduce the time for palindromic checks to O(1) by reusing some previous computation?