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. You are given two strings and want to find the length of the longest substring that appears in both strings contiguously. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Longest Common Subsequence DP approach that allows skipping characters

B. Greedy approach that extends matching characters until a mismatch occurs

C. Dynamic Programming that builds a 2D table tracking lengths of matching suffixes

D. Sorting all substrings of both strings and finding the longest common prefix

Solution

1. Step 1: Understand problem requires contiguous matching substrings

   Longest Common Substring requires contiguous characters, so subsequence approaches that allow gaps won't work.

2. Step 2: Identify DP approach tracking matching suffix lengths

   Dynamic Programming with a 2D table (or optimized 1D) that stores lengths of matching suffixes at each index pair guarantees optimal solution.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Only DP tracking contiguous matches solves this optimally [OK]

Hint: Longest common substring requires contiguous DP, not subsequence [OK]

Common Mistakes:

• Confusing substring with subsequence
• Trying greedy extension only
• Sorting substrings is inefficient

2. Consider the following Python code for longest palindromic subsequence. What is the value of dp[4] after the outer loop iteration with i = 2 when input string is 'abba'?

easy

A. 3

B. 1

C. 2

D. 4

Solution

1. Step 1: Trace dp array before i=2 iteration

   Initially dp = [1,1,1,1]. After i=3 iteration, dp remains [1,1,1,1].

2. Step 2: Update dp for i=2 (s[2]='b')

   For j=3 (s[3]='a'), s[2]!=s[3], dp[3] = max(dp[3], dp[2]) = max(1,1)=1. So dp[3]=1. prev updated accordingly. dp array after iteration: dp=[1,1,1,1].

3. Step 3: Clarify indexing

   dp[4] is out of range since dp has indices 0 to 3. Assuming question means dp[3], the value is 1 after i=2 iteration.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   dp[3] after i=2 iteration is 1, matching 1 [OK]

Hint: Trace dp updates carefully with indices [OK]

Common Mistakes:

• Off-by-one indexing
• Confusing dp[j] and dp[j-1]
• Misunderstanding prev variable

3. The following code attempts to implement the space-optimized bottom-up DP for the Delete Operation for Two Strings problem. Which line contains a subtle bug that can cause incorrect results or index errors?

medium

A. Line 7: for i in range(m - 1, -1, -1):

B. Line 12: dp[j] = 1 + min(dp[j], dp[j + 1])

C. Line 10: if word1[j] == word2[j]:

D. Line 14: prev = temp

Solution

1. Step 1: Identify indices used in inner loop

   Inner loop iterates j over word2 indices; word1 index should be i, not j.

2. Step 2: Spot incorrect character comparison

   Line 10 compares word1[j] instead of word1[i], mixing indices causes wrong subproblem computations.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Correct index usage is critical for DP correctness [OK]

Hint: Check index variables carefully in nested loops [OK]

Common Mistakes:

• Mixing i and j indices
• Incorrect base case initialization
• Wrong iteration order

4. Suppose you want to find the longest common substring between two strings, but now substrings can be formed by reusing characters multiple times (i.e., characters can be repeated any number of times). Which modification to the DP approach correctly handles this variant?

hard

A. Use the same DP but allow dp[j] to accumulate without resetting to zero on mismatch

B. Modify DP to allow transitions from dp[j] and dp[j-1] to handle reuse, iterating forward over j

C. Use a suffix automaton or suffix trie data structure instead of DP

D. Apply longest common subsequence DP since reuse allows gaps and repeats

Solution

1. Step 1: Understand reuse means characters can be matched multiple times

   Longest common substring with reuse breaks contiguity and requires allowing repeated matches.

2. Step 2: Modify DP to allow reuse by iterating forward and allowing dp[j] to build on itself

   Iterating forward over j and allowing dp[j] to depend on dp[j] and dp[j-1] enables reuse of characters multiple times.

3. Step 3: Recognize other options fail

   Resetting dp on mismatch breaks reuse, suffix automaton is complex but not DP, subsequence DP allows gaps but not reuse as described.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Forward iteration with reuse transitions correctly models repeated characters [OK]

Hint: Reuse requires forward iteration and dp[j] depending on itself [OK]

Common Mistakes:

• Not resetting dp breaks reuse
• Using subsequence DP incorrectly
• Ignoring iteration order for reuse

5. Suppose you want to find the longest palindromic substring in a string where characters can be added or removed dynamically, and you need to support queries efficiently. Which approach is best suited to handle this follow-up?

hard

A. Use the same DP tabulation approach on the entire string for each query

B. Use a suffix tree or suffix automaton to find palindromic substrings efficiently

C. Use Manacher's algorithm combined with segment trees or balanced BSTs for dynamic updates

D. Use brute force palindrome checks for each query since updates are rare

Solution

1. Step 1: Understand dynamic updates requirement

   DP tabulation recomputes entire table O(n^2) per query, inefficient for dynamic changes.

2. Step 2: Identify suitable data structures

   Manacher's algorithm finds longest palindrome in O(n), but not dynamic. Combining it with segment trees or balanced BSTs allows efficient updates and queries.

3. Step 3: Evaluate other options

   Suffix trees/automata help substring queries but not specifically palindromes with dynamic updates. Brute force is too slow.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Dynamic palindrome queries require advanced data structures [OK]

Hint: Dynamic palindrome queries need specialized data structures [OK]

Common Mistakes:

• Re-running DP for each query
• Using suffix trees without palindrome focus
• Ignoring update complexity