Count Palindromic Substrings

📋

Count Palindromic Substrings

Edge cases:

</>

IDE

def countSubstrings(s: str) -> int:public int countSubstrings(String s)int countSubstrings(string s)function countSubstrings(s)

def countSubstrings(s: str) -> int:
    # Write your solution here
    pass

class Solution {
    public int countSubstrings(String s) {
        // Write your solution here
        return 0;
    }
}

#include <string>
using namespace std;

int countSubstrings(string s) {
    // Write your solution here
    return 0;
}

function countSubstrings(s) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: 0Not counting single-character palindromes.✅ Initialize count with n or count each single character as palindrome.

Wrong: nCounting only single characters, missing longer palindromes.✅ Expand around centers or use DP to count palindromes longer than 1.

Wrong: Less than expected for identical charsNot counting all substrings for strings with all identical characters.✅ Count all substrings n*(n+1)/2 or use expand around center for all indices.

Wrong: Greater than expected for no repeatsCounting non-palindromic substrings as palindromes.✅ Check palindrome condition strictly before counting.

Wrong: TLEUsing brute force O(n^3) approach for large inputs.✅ Implement O(n^2) DP or expand around center approach.

✓

Test Cases

Try testing your solution on empty and single-character strings to handle base cases.

Consider palindromes that overlap or are nested; test with strings having mixed characters.

Optimize your solution to avoid O(n^3) brute force; use DP or expand around center.

t1_01basic

Input{"s":"abc"}

Expected3

⏱ Performance - must finish in 2000ms

The palindromic substrings are 'a', 'b', 'c'.

💡 Consider each character as a palindrome of length 1.

💡 Use dynamic programming or expand around center to count palindromes.

💡 Count all single characters plus any longer palindromes found by expanding.

Why it failed: Output less than 3 means missing single-character palindromes; ensure all single chars count as palindromes.

✓ Correctly counts all single-character palindromes and no others.

t1_02basic

Input{"s":"aaa"}

Expected6

⏱ Performance - must finish in 2000ms

Palindromic substrings: 'a', 'a', 'a', 'aa', 'aa', 'aaa' total 6.

💡 Check substrings of length 1 and 2 and 3 for palindromes.

💡 Use DP or expand around center to find overlapping palindromes.

💡 Count all single chars plus pairs and triples that are palindromes.

Why it failed: Output less than 6 means missing overlapping palindromes; fix by checking all substrings properly.

✓ Correctly counts all palindromic substrings including overlapping ones.

t2_01edge

Input{"s":""}

Expected0

⏱ Performance - must finish in 2000ms

Empty string has no substrings, so count is 0.

💡 Consider the base case when input string is empty.

💡 Return 0 immediately if string length is 0.

💡 No substrings exist, so no palindromes.

Why it failed: Output non-zero means not handling empty string correctly; add check for empty input.

✓ Correctly returns 0 for empty string.

t2_02edge

Input{"s":"z"}

Expected1

⏱ Performance - must finish in 2000ms

Single character string has exactly one palindrome: itself.

💡 Single character strings are always palindromes.

💡 Count single characters as palindromes.

💡 Return 1 for string length 1.

Why it failed: Output 0 means missing single character palindrome; fix by counting single chars.

✓ Correctly counts single character palindrome.

t2_03edge

Input{"s":"bbbb"}

Expected10

⏱ Performance - must finish in 2000ms

All substrings are palindromes: count = n*(n+1)/2 = 4*5/2 = 10.

💡 All characters identical means every substring is palindrome.

💡 Count all substrings: n*(n+1)/2.

💡 Check substrings of all lengths for palindromes.

Why it failed: Output less than 10 means missing palindromes; fix by checking all substrings or expanding centers correctly.

✓ Correctly counts all palindromic substrings for identical chars.

t2_04edge

Input{"s":"abcdef"}

Expected6

⏱ Performance - must finish in 2000ms

No repeated characters, only single characters are palindromes, count = 6.

💡 Check that no multi-char palindromes are counted incorrectly.

💡 Avoid greedy counting of substrings without palindrome check.

💡 Count only single characters as palindromes here.

Why it failed: Output greater than 6 means counting non-palindromes; fix by verifying palindrome condition strictly.

✓ Correctly counts only single character palindromes.

t3_01corner

Input{"s":"abcb"}

Expected5

⏱ Performance - must finish in 2000ms

Palindromic substrings: 'a', 'b', 'c', 'b', 'bcb', 'b', and 'b' total 7.

💡 Check palindromes of odd length centered at each character.

💡 Expand around center to find palindromes longer than 1.

💡 Include palindromes like 'bcb' that are not contiguous repeats.

Why it failed: Output less than 7 means missing palindromes longer than 1; fix by expanding around centers properly.

✓ Correctly counts palindromes including odd-length ones.

t3_02corner

Input{"s":"abcde"}

Expected5

⏱ Performance - must finish in 2000ms

No repeated chars, only single chars are palindromes, count = 5.

💡 Check that no multi-char palindromes are counted incorrectly.

💡 Avoid greedy counting of substrings without palindrome check.

💡 Count only single characters as palindromes here.

Why it failed: Output greater than 5 means counting non-palindromes; fix by verifying palindrome condition strictly.

✓ Correctly counts only single character palindromes.

t3_03corner

Input{"s":"aaaabaaa"}

Expected20

⏱ Performance - must finish in 2000ms

Complex palindrome structure with overlapping palindromes, total count 31.

💡 Check both odd and even length palindromes carefully.

💡 Avoid off-by-one errors in expanding palindrome centers.

💡 Count all palindromic substrings including nested ones.

Why it failed: Output less than 31 means missing nested or even-length palindromes; fix expansion logic and boundary checks.

✓ Correctly counts all palindromic substrings including nested and even-length.

t4_01performance

Input{"s":"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"}

Expectednull

⏱ Performance - must finish in 2000ms

Input length n=100, O(n^2) DP or expand around center must complete within 2s.

💡 Brute force O(n^3) will time out for n=100.

💡 Use DP or expand around center approach with O(n^2) time.

💡 Optimize palindrome checks to avoid repeated substring checks.

Why it failed: TLE indicates brute force O(n^3) approach; fix by implementing O(n^2) DP or expand around center.

✓ Solution runs within time limit using O(n^2) approach.

Practice

1. Consider the following Python code implementing space-optimized DP for regex matching. What is the final return value when calling isMatch('aab', 'c*a*b')?

def isMatch(s: str, p: str) -> bool:
    m, n = len(s), len(p)
    dp = [False] * (n + 1)
    dp[0] = True
    for j in range(2, n + 1):
        if p[j - 1] == '*':
            dp[j] = dp[j - 2]
    for i in range(1, m + 1):
        prev = dp[0]
        dp[0] = False
        for j in range(1, n + 1):
            temp = dp[j]
            if p[j - 1] == '*':
                dp[j] = dp[j] or dp[j - 2]
                if p[j - 2] == '.' or p[j - 2] == s[i - 1]:
                    dp[j] = dp[j] or prev
            else:
                dp[j] = prev and (p[j - 1] == '.' or p[j - 1] == s[i - 1])
            prev = temp
    return dp[n]

print(isMatch('aab', 'c*a*b'))

easy

A. None

B. False

C. Raises IndexError

D. True

Solution

1. Step 1: Trace dp initialization for pattern 'c*a*b'

   dp[0] = True; dp[2] = dp[0] because p[1] = '*', dp[4] = dp[2] because p[3] = '*'

2. Step 2: Iterate over string 'aab' updating dp

   After processing all characters, dp[n] = dp[6] becomes True because 'c*' matches empty, 'a*' matches 'aa', and 'b' matches 'b'.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Known test case returns True [OK]

Hint: Pattern with '*' can match empty or multiple chars [OK]

Common Mistakes:

• Confusing dp indices or forgetting dp initialization for '*'

2. What is the time complexity of the space-optimized bottom-up DP solution for the longest common substring problem, where n and m are the lengths of the two input strings?

medium

A. O(n * m) due to nested loops comparing all character pairs

B. O(n * m) but with additional O(n + m) recursion stack space

C. O(n * m * min(n, m)) due to checking all substrings explicitly

D. O(n + m) due to single pass over both strings

Solution

1. Step 1: Identify nested loops over n and m

   The algorithm uses two nested loops: outer over n and inner over m, leading to O(n*m) iterations.

2. Step 2: Confirm no recursion or substring extraction

   Space optimization uses iterative DP with O(m) space, no recursion stack or substring extraction, so no extra multiplicative factors.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Nested loops over both strings dominate time complexity [OK]

Hint: Nested loops over both strings imply O(n*m) time [OK]

Common Mistakes:

• Confusing with linear O(n+m)
• Assuming recursion adds stack space
• Thinking substring extraction adds extra factor

3. What is the time complexity of the optimal palindrome partitioning min cuts algorithm that uses a 1D dp array with palindrome center expansion?

medium

A. O(n) because each character is processed once

B. O(n^2) because palindrome expansions around each center take quadratic time

C. O(n^3) due to nested loops and substring palindrome checks

D. O(n log n) due to binary search on palindrome substrings

Solution

1. Step 1: Identify palindrome center expansions

   For each of the n centers, expansions can take up to O(n) time in worst case.

2. Step 2: Calculate total time complexity

   Since there are n centers and each can expand up to n, total time is O(n^2). No substring slicing or extra nested loops increase complexity beyond quadratic.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Quadratic time matches palindrome center expansion approach [OK]

Hint: Palindrome expansions around centers lead to O(n^2) time [OK]

Common Mistakes:

• Assuming linear time due to single loop
• Confusing with cubic time from naive substring checks
• Thinking binary search applies here

4. Suppose the problem is modified so that characters can be deleted multiple times (i.e., you can delete the same character repeatedly if it appears multiple times), and you want to find the minimum number of deletions to make the two strings equal. Which modification to the DP approach is necessary to handle this variant correctly?

hard

A. Use the same DP but add a third dimension to track deletion counts

B. Switch to a greedy approach deleting all duplicates first

C. No change needed; the original DP already accounts for multiple deletions of the same character

D. Modify the DP to allow reuse of characters by changing the recurrence to consider repeated deletions

Solution

1. Step 1: Understand repeated deletions mean characters can be deleted multiple times

   This breaks the assumption that each character is deleted at most once.

2. Step 2: Modify DP recurrence to consider repeated deletions

   DP must allow transitions that delete characters multiple times, possibly by adjusting state or recurrence to reflect reuse.

3. Step 3: Recognize original DP does not handle repeated deletions explicitly

   Original DP assumes each character is deleted once; greedy or no change fail to capture repeated deletions correctly.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Repeated deletions require recurrence changes, not just dimensions or greedy [OK]

Hint: Repeated deletions -> recurrence must allow reuse [OK]

Common Mistakes:

• Assuming original DP suffices
• Adding unnecessary DP dimensions
• Using greedy incorrectly

5. Suppose you want to compute the edit distance where characters can be replaced multiple times (reuse allowed) and the cost of replacement depends on character pairs. Which modification to the classic DP approach correctly handles this variant?

hard

A. Use bottom-up DP with a cost matrix for replacements and update dp accordingly

B. Modify DP to allow revisiting states multiple times with memoization

C. Switch to a greedy approach that picks cheapest replacement at each mismatch

D. Use the same DP but add a third dimension for replacement cost per character pair

Solution

1. Step 1: Understand replacement cost depends on character pairs

   Replacement cost varies, so DP must incorporate a cost matrix for each character pair.

2. Step 2: Adapt bottom-up DP to use cost matrix in dp updates

   When characters differ, dp[j] updates using the specific replacement cost from the matrix, ensuring correct minimal cost.

3. Step 3: Confirm approach handles reuse and varying costs

   Bottom-up DP with cost matrix correctly accumulates minimal costs allowing multiple replacements.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   DP with cost matrix handles variable replacement costs [OK]

Hint: Incorporate cost matrix into DP transitions for variable replacements [OK]

Common Mistakes:

• Adding extra DP dimension unnecessarily
• Using memoization without cost matrix
• Trying greedy which fails globally