Palindromic Substrings - Practice Coding Problems

Palindromic Substrings - Problem

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.

Input & Output

Example 1 — Basic Case

$ Input: s = "abc"

› Output: 3

💡 Note: Three palindromic substrings: "a", "b", "c". Each single character is a palindrome.

Example 2 — With Longer Palindromes

$ Input: s = "aaa"

› Output: 6

💡 Note: Six palindromic substrings: "a", "a", "a", "aa", "aa", "aaa". Multiple overlapping palindromes exist.

Example 3 — Mixed Palindromes

$ Input: s = "aba"

› Output: 4

💡 Note: Four palindromic substrings: "a" at index 0, "b" at index 1, "a" at index 2, and "aba" spanning the whole string.

Constraints

1 ≤ s.length ≤ 1000
s consists of lowercase English letters

Visualization

Tap to expand

Understanding the Visualization

Input String

Given string with characters to analyze

Find Palindromes

Identify all substrings that read same forwards and backwards

Count Total

Return the total number of palindromic substrings

Key Takeaway

🎯 Key Insight: Every palindrome has a center - expand around each possible center to find all palindromic substrings efficiently

Asked in

f Facebook 45 G Google 38 a Amazon 32 M Microsoft 28

The key insight is that every palindrome expands around a center. The optimal expand around centers approach checks each possible center (single characters and between characters) and expands outward while characters match. Time: O(n²), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Check All Substrings	O(n³)	O(1)	Generate all possible substrings and check each one for palindrome property
Dynamic Programming Table	O(n²)	O(n²)	Build a 2D table where dp[i][j] indicates if substring from i to j is palindrome
Expand Around Centers	O(n²)	O(1)	For each possible center, expand outwards while characters match

Brute Force - Check All Substrings — Algorithm Steps

Generate all possible substrings using nested loops
For each substring, check if it's a palindrome by comparing characters
Count total palindromic substrings

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Substrings

Create all possible contiguous substrings

Check Palindromes

Test each substring by comparing with its reverse

Count Results

Sum up all palindromic substrings found

Code -

solution.c — C

#include <stdio.h>
#include <string.h>
#include <stdbool.h>

bool isPalindrome(char* str, int start, int end) {
    while (start < end) {
        if (str[start] != str[end]) {
            return false;
        }
        start++;
        end--;
    }
    return true;
}

int solution(char* s) {
    int count = 0;
    int n = strlen(s);
    
    // Generate all substrings
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            // Check if substring is palindrome
            if (isPalindrome(s, i, j)) {
                count++;
            }
        }
    }
    
    return count;
}

int main() {
    char s[1001];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    printf("%d\n", solution(s));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

Two nested loops to generate O(n²) substrings, O(n) time to check each palindrome

⚠ Quadratic Growth

Space Complexity

O(1)

Only using a few variables for counting and iteration

✓ Linear Space

285.0K Views

High Frequency

~15 min Avg. Time

8.5K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Check All Substrings — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler