Longest Palindromic Substring

🎯

Longest Palindromic Substring

mediumDPAmazonMicrosoftGoogle

Imagine you are analyzing DNA sequences and want to find the longest palindromic segment, which might indicate a special biological property.

💡 This problem asks for the longest contiguous substring that reads the same forwards and backwards. Beginners often confuse substrings with subsequences and struggle to efficiently check all possible substrings.

📋

Problem Statement

Given a string s, find the longest substring which is a palindrome. Return the substring itself.

1 ≤ n ≤ 10^5s consists of only ASCII characters

💡

Example

Input"babad"

Outputbab

The longest palindromic substring is 'bab' (or 'aba'). Both are valid answers.

Input"cbbd"

Outputbb

The longest palindromic substring is 'bb'.

• Single character string → the character itself
• All characters same → entire string
• No palindrome longer than 1 → any single character
• Palindrome at the start or end of string → correctly identified

🔁

Why DP?

Why greedy fails:

A greedy approach might pick the first palindrome found or expand only from one side, missing longer palindromes elsewhere. For example, in 'abacdfgdcaba', greedily expanding from the start misses the longer palindrome 'aba' at the end.

DP state:

dp[i][w] = True if the substring starting at index i with length w is a palindrome, else False.

Recurrence:dp[i][w] = (s[i] == s[i+w-1]) AND (w <= 3 OR dp[i+1][w-2])

A substring is palindrome if its first and last characters match and the substring inside is palindrome (or length ≤ 3).

⚠️

Common Mistakes

Confusing substring with subsequence

Incorrect answers or misunderstanding problem constraints

✅ Clarify substring means contiguous characters

Not handling even length palindromes in center expansion

Misses palindromes like 'bb' or 'abba'

✅ Expand around centers at i and i+1 as well as i alone

Incorrect DP table fill order

Accessing dp[i+1][j-1] before it is computed leads to wrong results

✅ Fill dp by increasing substring length

Off-by-one errors in substring indices

Wrong substring returned or runtime errors

✅ Carefully track start and end indices and substring slicing

Not updating longest palindrome when length equals current max

May return shorter palindrome when multiple longest exist

✅ Update only if strictly longer or handle ties explicitly

🧠

Brute Force (Check All Substrings)

💡 This approach exists to build intuition by exhaustively checking every substring, which helps understand the problem's nature and why optimization is needed.

Intuition

Check every possible substring and verify if it is a palindrome by comparing characters from both ends.

Algorithm

1. Generate all possible substrings of the input string.
2. For each substring, check if it is a palindrome by comparing characters from start and end.
3. Keep track of the longest palindrome found so far.
4. Return the longest palindrome substring after checking all.

💡 The nested loops and palindrome checks make it hard to see the inefficiency at first glance.

Recurrence:Not applicable for pure brute force.

</>

Code

def longest_palindrome_brute(s: str) -> str:
    n = len(s)
    max_len = 1
    start = 0
    def is_palindrome(l, r):
        while l < r:
            if s[l] != s[r]:
                return False
            l += 1
            r -= 1
        return True
    for i in range(n):
        for j in range(i, n):
            if is_palindrome(i, j) and (j - i + 1) > max_len:
                start = i
                max_len = j - i + 1
    return s[start:start+max_len]

# Driver code
if __name__ == '__main__':
    print(longest_palindrome_brute('babad'))  # Expected: 'bab' or 'aba'

Line Notes

def longest_palindrome_brute(s: str) -> str:Defines the main function to find longest palindrome substring

def is_palindrome(l, r):Helper function to check palindrome between indices l and r

while l < r:Loop to compare characters from both ends moving towards center

for i in range(n):Outer loop selects start index of substring

for j in range(i, n):Inner loop selects end index of substring

if is_palindrome(i, j) and (j - i + 1) > max_len:Update longest palindrome if current substring is palindrome and longer

public class Solution {
    public static String longestPalindromeBrute(String s) {
        int n = s.length();
        int maxLen = 1, start = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                if (isPalindrome(s, i, j) && (j - i + 1) > maxLen) {
                    start = i;
                    maxLen = j - i + 1;
                }
            }
        }
        return s.substring(start, start + maxLen);
    }
    private static boolean isPalindrome(String s, int l, int r) {
        while (l < r) {
            if (s.charAt(l) != s.charAt(r)) return false;
            l++;
            r--;
        }
        return true;
    }
    public static void main(String[] args) {
        System.out.println(longestPalindromeBrute("babad")); // Expected: 'bab' or 'aba'
    }
}

Line Notes

public static String longestPalindromeBrute(String s)Main method to find longest palindrome substring

for (int i = 0; i < n; i++)Outer loop picks start index

for (int j = i; j < n; j++)Inner loop picks end index

if (isPalindrome(s, i, j) && (j - i + 1) > maxLen)Update longest palindrome if current substring is palindrome and longer

#include <iostream>
#include <string>
using namespace std;

bool isPalindrome(const string &s, int l, int r) {
    while (l < r) {
        if (s[l] != s[r]) return false;
        l++;
        r--;
    }
    return true;
}

string longestPalindromeBrute(const string &s) {
    int n = s.size();
    int maxLen = 1, start = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            if (isPalindrome(s, i, j) && (j - i + 1) > maxLen) {
                start = i;
                maxLen = j - i + 1;
            }
        }
    }
    return s.substr(start, maxLen);
}

int main() {
    cout << longestPalindromeBrute("babad") << endl; // Expected: 'bab' or 'aba'
    return 0;
}

Line Notes

bool isPalindrome(const string &s, int l, int r)Helper function to check palindrome between indices l and r

for (int i = 0; i < n; i++)Outer loop selects start index

for (int j = i; j < n; j++)Inner loop selects end index

if (isPalindrome(s, i, j) && (j - i + 1) > maxLen)Update longest palindrome if current substring is palindrome and longer

function longestPalindromeBrute(s) {
    const n = s.length;
    let maxLen = 1;
    let start = 0;
    function isPalindrome(l, r) {
        while (l < r) {
            if (s[l] !== s[r]) return false;
            l++;
            r--;
        }
        return true;
    }
    for (let i = 0; i < n; i++) {
        for (let j = i; j < n; j++) {
            if (isPalindrome(i, j) && (j - i + 1) > maxLen) {
                start = i;
                maxLen = j - i + 1;
            }
        }
    }
    return s.substring(start, start + maxLen);
}

console.log(longestPalindromeBrute('babad')); // Expected: 'bab' or 'aba'

Line Notes

function longestPalindromeBrute(s)Main function to find longest palindrome substring

function isPalindrome(l, r)Helper function to check palindrome between indices l and r

for (let i = 0; i < n; i++)Outer loop picks start index

for (let j = i; j < n; j++)Inner loop picks end index

if (isPalindrome(i, j) && (j - i + 1) > maxLen)Update longest palindrome if current substring is palindrome and longer

⏱

Complexity

TimeO(n^3)

SpaceO(1)

There are O(n^2) substrings and each palindrome check takes O(n), totaling O(n^3).

💡 For n=20, this means about 8000 checks, which is slow but still manageable for small inputs.

Interview Verdict: TLE for large inputs, useful only to introduce the problem

Shows why brute force is impractical and motivates optimization.

🧠

Expand Around Center

💡 This approach improves efficiency by exploiting the palindrome property that it mirrors around its center, reducing redundant checks.

Intuition

Every palindrome can be expanded from its center. Check all centers (single characters and between characters) and expand outwards to find the longest palindrome.

Algorithm

1. Iterate over each index as a potential palindrome center.
2. Expand around the center for odd-length palindromes.
3. Expand around the center and next index for even-length palindromes.
4. Track the longest palindrome found during expansions.
5. Return the longest palindrome substring.

💡 The dual expansion for odd and even length palindromes is key and can be tricky to implement correctly.

Recurrence:Not a classic DP recurrence but uses center expansion logic.

</>

Code

def longest_palindrome_expand(s: str) -> str:
    if not s:
        return ""
    start, end = 0, 0
    def expand_around_center(left, right):
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return left + 1, right - 1
    for i in range(len(s)):
        l1, r1 = expand_around_center(i, i)
        l2, r2 = expand_around_center(i, i + 1)
        if r1 - l1 > end - start:
            start, end = l1, r1
        if r2 - l2 > end - start:
            start, end = l2, r2
    return s[start:end+1]

# Driver code
if __name__ == '__main__':
    print(longest_palindrome_expand('babad'))  # Expected: 'bab' or 'aba'

Line Notes

def expand_around_center(left, right):Helper to expand palindrome around given center indices

while left >= 0 and right < len(s) and s[left] == s[right]:Expand as long as characters match and indices valid

for i in range(len(s))Try every index as center for odd and even length palindromes

if r1 - l1 > end - start:Update longest palindrome if found longer odd-length palindrome

if r2 - l2 > end - start:Update longest palindrome if found longer even-length palindrome

return s[start:end+1]Return the longest palindrome substring found

public class Solution {
    public static String longestPalindromeExpand(String s) {
        if (s == null || s.length() < 1) return "";
        int start = 0, end = 0;
        for (int i = 0; i < s.length(); i++) {
            int len1 = expandAroundCenter(s, i, i);
            int len2 = expandAroundCenter(s, i, i + 1);
            int len = Math.max(len1, len2);
            if (len > end - start) {
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }
        return s.substring(start, end + 1);
    }
    private static int expandAroundCenter(String s, int left, int right) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        return right - left - 1;
    }
    public static void main(String[] args) {
        System.out.println(longestPalindromeExpand("babad")); // Expected: 'bab' or 'aba'
    }
}

Line Notes

for (int i = 0; i < s.length(); i++)Iterate over each character as center

int len1 = expandAroundCenter(s, i, i);Check odd length palindrome

int len2 = expandAroundCenter(s, i, i + 1);Check even length palindrome

if (len > end - start)Update longest palindrome boundaries if longer found

#include <iostream>
#include <string>
using namespace std;

int expandAroundCenter(const string &s, int left, int right) {
    while (left >= 0 && right < (int)s.size() && s[left] == s[right]) {
        left--;
        right++;
    }
    return right - left - 1;
}

string longestPalindromeExpand(const string &s) {
    if (s.empty()) return "";
    int start = 0, end = 0;
    for (int i = 0; i < (int)s.size(); i++) {
        int len1 = expandAroundCenter(s, i, i);
        int len2 = expandAroundCenter(s, i, i + 1);
        int len = max(len1, len2);
        if (len > end - start) {
            start = i - (len - 1) / 2;
            end = i + len / 2;
        }
    }
    return s.substr(start, end - start + 1);
}

int main() {
    cout << longestPalindromeExpand("babad") << endl; // Expected: 'bab' or 'aba'
    return 0;
}

Line Notes

int expandAroundCenter(const string &s, int left, int right)Helper to expand palindrome from center indices

while (left >= 0 && right < (int)s.size() && s[left] == s[right])Expand while characters match and indices valid

for (int i = 0; i < (int)s.size(); i++)Try each index as center for odd and even palindromes

if (len > end - start)Update longest palindrome boundaries if longer palindrome found

function longestPalindromeExpand(s) {
    if (!s) return "";
    let start = 0, end = 0;
    function expandAroundCenter(left, right) {
        while (left >= 0 && right < s.length && s[left] === s[right]) {
            left--;
            right++;
        }
        return right - left - 1;
    }
    for (let i = 0; i < s.length; i++) {
        let len1 = expandAroundCenter(i, i);
        let len2 = expandAroundCenter(i, i + 1);
        let len = Math.max(len1, len2);
        if (len > end - start) {
            start = i - Math.floor((len - 1) / 2);
            end = i + Math.floor(len / 2);
        }
    }
    return s.substring(start, end + 1);
}

console.log(longestPalindromeExpand('babad')); // Expected: 'bab' or 'aba'

Line Notes

function expandAroundCenter(left, right)Helper to expand palindrome around center indices

while (left >= 0 && right < s.length && s[left] === s[right])Expand while characters match and indices valid

for (let i = 0; i < s.length; i++)Try each index as center for odd and even palindromes

if (len > end - start)Update longest palindrome boundaries if longer palindrome found

⏱

Complexity

TimeO(n^2)

SpaceO(1)

Each center expansion takes O(n) and there are O(n) centers, totaling O(n^2).

💡 For n=20, about 400 expansions, which is efficient for typical interview constraints.

Interview Verdict: Accepted and efficient for medium-sized inputs

A practical and commonly accepted solution in interviews.

🧠

Dynamic Programming (Tabulation)

💡 This approach uses a DP table to store palindrome status of substrings, avoiding repeated checks and enabling bottom-up computation.

Intuition

Build a 2D table where dp[i][j] indicates if substring s[i..j] is palindrome. Use smaller substrings to build larger ones.

Algorithm

1. Initialize a 2D boolean dp table of size n x n.
2. Mark all substrings of length 1 as palindrome.
3. Check substrings of length 2 and mark palindrome if both chars equal.
4. For substrings length ≥ 3, dp[i][j] = (s[i] == s[j]) AND dp[i+1][j-1].
5. Track the longest palindrome substring during filling.
6. Return the longest palindrome substring found.

💡 The order of filling the table by substring length is crucial to ensure dependencies are computed first.

Recurrence:dp[i][j] = (s[i] == s[j]) AND (j - i < 3 OR dp[i+1][j-1])

</>

Code

def longest_palindrome_dp(s: str) -> str:
    n = len(s)
    if n == 0:
        return ""
    dp = [[False] * n for _ in range(n)]
    start, max_len = 0, 1
    for i in range(n):
        dp[i][i] = True
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            if s[i] == s[j]:
                if length <= 3:
                    dp[i][j] = True
                else:
                    dp[i][j] = dp[i + 1][j - 1]
            else:
                dp[i][j] = False
            if dp[i][j] and length > max_len:
                start = i
                max_len = length
    return s[start:start + max_len]

# Driver code
if __name__ == '__main__':
    print(longest_palindrome_dp('babad'))  # Expected: 'bab' or 'aba'

Line Notes

dp = [[False] * n for _ in range(n)]Initialize DP table to store palindrome status

for i in range(n): dp[i][i] = TrueAll single characters are palindromes

for length in range(2, n + 1)Check all substring lengths from 2 to n

for i in range(n - length + 1)Iterate over all possible start indices for current length

if s[i] == s[j]Check if substring ends match to consider palindrome

if length <= 3: dp[i][j] = TrueSubstrings of length 2 or 3 are palindrome if ends match

else: dp[i][j] = dp[i + 1][j - 1]Use inner substring palindrome status for longer substrings

if dp[i][j] and length > max_lenUpdate longest palindrome substring found

public class Solution {
    public static String longestPalindromeDP(String s) {
        int n = s.length();
        if (n == 0) return "";
        boolean[][] dp = new boolean[n][n];
        int start = 0, maxLen = 1;
        for (int i = 0; i < n; i++) dp[i][i] = true;
        for (int length = 2; length <= n; length++) {
            for (int i = 0; i <= n - length; i++) {
                int j = i + length - 1;
                if (s.charAt(i) == s.charAt(j)) {
                    if (length <= 3) dp[i][j] = true;
                    else dp[i][j] = dp[i + 1][j - 1];
                } else {
                    dp[i][j] = false;
                }
                if (dp[i][j] && length > maxLen) {
                    start = i;
                    maxLen = length;
                }
            }
        }
        return s.substring(start, start + maxLen);
    }
    public static void main(String[] args) {
        System.out.println(longestPalindromeDP("babad")); // Expected: 'bab' or 'aba'
    }
}

Line Notes

boolean[][] dp = new boolean[n][n];DP table initialization

for (int i = 0; i < n; i++) dp[i][i] = true;Single characters are palindromes

for (int length = 2; length <= n; length++)Iterate over substring lengths

for (int i = 0; i <= n - length; i++)Iterate over start indices for current length

if (s.charAt(i) == s.charAt(j))Check if substring ends match

if (length <= 3) dp[i][j] = true;Substrings of length 2 or 3 are palindrome if ends match

else dp[i][j] = dp[i + 1][j - 1];Use inner substring palindrome status

if (dp[i][j] && length > maxLen)Update longest palindrome substring

#include <iostream>
#include <string>
#include <vector>
using namespace std;

string longestPalindromeDP(const string &s) {
    int n = s.size();
    if (n == 0) return "";
    vector<vector<bool>> dp(n, vector<bool>(n, false));
    int start = 0, maxLen = 1;
    for (int i = 0; i < n; i++) dp[i][i] = true;
    for (int length = 2; length <= n; length++) {
        for (int i = 0; i <= n - length; i++) {
            int j = i + length - 1;
            if (s[i] == s[j]) {
                if (length <= 3) dp[i][j] = true;
                else dp[i][j] = dp[i + 1][j - 1];
            } else {
                dp[i][j] = false;
            }
            if (dp[i][j] && length > maxLen) {
                start = i;
                maxLen = length;
            }
        }
    }
    return s.substr(start, maxLen);
}

int main() {
    cout << longestPalindromeDP("babad") << endl; // Expected: 'bab' or 'aba'
    return 0;
}

Line Notes

vector<vector<bool>> dp(n, vector<bool>(n, false));Initialize DP table with false

for (int i = 0; i < n; i++) dp[i][i] = true;Single characters are palindromes

for (int length = 2; length <= n; length++)Iterate over substring lengths

for (int i = 0; i <= n - length; i++)Iterate over start indices for current length

if (s[i] == s[j])Check if substring ends match

if (length <= 3) dp[i][j] = true;Substrings of length 2 or 3 are palindrome if ends match

else dp[i][j] = dp[i + 1][j - 1];Use inner substring palindrome status

if (dp[i][j] && length > maxLen)Update longest palindrome substring

function longestPalindromeDP(s) {
    const n = s.length;
    if (n === 0) return "";
    const dp = Array.from({ length: n }, () => Array(n).fill(false));
    let start = 0, maxLen = 1;
    for (let i = 0; i < n; i++) dp[i][i] = true;
    for (let length = 2; length <= n; length++) {
        for (let i = 0; i <= n - length; i++) {
            let j = i + length - 1;
            if (s[i] === s[j]) {
                if (length <= 3) dp[i][j] = true;
                else dp[i][j] = dp[i + 1][j - 1];
            } else {
                dp[i][j] = false;
            }
            if (dp[i][j] && length > maxLen) {
                start = i;
                maxLen = length;
            }
        }
    }
    return s.substring(start, start + maxLen);
}

console.log(longestPalindromeDP('babad')); // Expected: 'bab' or 'aba'

Line Notes

const dp = Array.from({ length: n }, () => Array(n).fill(false));Initialize 2D DP array with false

for (let i = 0; i < n; i++) dp[i][i] = true;Single characters are palindromes

for (let length = 2; length <= n; length++)Iterate over substring lengths

for (let i = 0; i <= n - length; i++)Iterate over start indices for current length

if (s[i] === s[j])Check if substring ends match

if (length <= 3) dp[i][j] = true;Substrings of length 2 or 3 are palindrome if ends match

else dp[i][j] = dp[i + 1][j - 1];Use inner substring palindrome status

if (dp[i][j] && length > maxLen)Update longest palindrome substring

⏱

Complexity

TimeO(n^2)

SpaceO(n^2)

We fill an n x n table, each cell computed once, so O(n^2) time and space.

💡 For n=1000, this means about 1 million operations and memory cells, which is feasible but costly.

Interview Verdict: Accepted, but uses more memory than center expansion

Good to demonstrate DP skills, but less optimal in space than center expansion.

📊

All Approaches - One-Glance Tradeoffs

💡 Center expansion is the best balance of simplicity and efficiency for interviews.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n^3)	O(1)	No	Yes	Mention only - never code
2. Expand Around Center	O(n^2)	O(1)	No	Yes	Code this in 95% of interviews
3. Dynamic Programming (Tabulation)	O(n^2)	O(n^2)	No	Yes	Good to discuss for DP knowledge, but less preferred to code

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding each approach, and prepare to explain tradeoffs clearly.

How to Present

Clarify problem constraints and definitions (substring vs subsequence).State brute force approach and its inefficiency.Introduce expand around center as a practical optimization.Explain DP tabulation for completeness and DP understanding.Discuss time/space tradeoffs and edge cases.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 10min → Test: 3min. Total ~20min

What the Interviewer Tests

Ability to identify palindrome properties, optimize naive solutions, implement DP or center expansion correctly, and handle edge cases.

Common Follow-ups

• How to find the count of all palindromic substrings → Use DP to count all true dp[i][j]
• Can we do better than O(n^2)? → Manacher's algorithm achieves O(n) time

💡 These follow-ups test deeper understanding and knowledge of advanced algorithms.

🔍

Pattern Recognition

When to Use

1) Problem asks for longest palindromic substring or count of palindromic substrings; 2) Input is a string; 3) Requires contiguous characters; 4) Overlapping subproblems exist.

Signature Phrases

longest palindromic substringexpand around centersubstring palindrome check

NOT This Pattern When

Longest Palindromic Subsequence problems which allow non-contiguous characters

Similar Problems

Longest Palindromic Subsequence - similar but subsequence instead of substringPalindrome Partitioning - uses palindrome substring checks as subroutine

Practice

1. What is the time complexity of the space-optimized bottom-up dynamic programming solution for the edit distance problem, where m and n are the lengths of the two input strings?

medium

A. O(m + n)

B. O(m * n)

C. O(m * n * min(m, n))

D. O(m * n * log n)

Solution

1. Step 1: Identify nested loops over both strings

   The algorithm has two nested loops: outer over m and inner over n.

2. Step 2: Calculate total operations

   Each cell dp[j] is updated once per iteration, so total operations are proportional to m * n.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Double loop over m and n -> O(m*n) [OK]

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

Common Mistakes:

• Confusing with linear O(m+n)
• Adding extra factor min(m,n) incorrectly
• Assuming logarithmic factor

2. 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

3. What is the time and space complexity of the space-optimized bottom-up DP solution for the maximum uncrossed lines problem, where the input arrays have lengths m and n respectively?

medium

A. Time: O(m*n), Space: O(n)

B. Time: O(m+n), Space: O(m+n)

C. Time: O(m*n), Space: O(m*n)

D. Time: O(2^(m+n)), Space: O(m+n)

Solution

1. Step 1: Identify complexity of outer and inner loops

   The algorithm uses two nested loops: outer loop runs m times, inner loop runs n times, resulting in O(m*n) time complexity.

2. Step 2: Check if recursion stack adds extra space

   Space is optimized to a single dp array of size n+1, so space complexity is O(n), not O(m*n) or O(m+n).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Nested loops cause O(m*n) time; single dp array causes O(n) space [OK]

Hint: Nested loops -> O(m*n) time; single dp array -> O(n) space [OK]

Common Mistakes:

• Confusing recursion stack space with dp array space
• Assuming linear time due to optimization

4. Suppose the problem is modified so that you want to find the minimum cuts for palindrome partitioning but now the input string can contain wildcard characters '?' that can match any single character. Which of the following approaches correctly adapts the optimal DP solution to handle wildcards?

hard

A. Replace all '?' with all possible characters and run DP multiple times, taking minimum cuts over all results

B. Precompute all palindrome substrings ignoring '?', then run DP as usual

C. Use pure recursion with memoization since DP cannot handle wildcards efficiently

D. Modify palindrome checks to treat '?' as matching any character during center expansions, keeping the same DP structure

Solution

1. Step 1: Understand wildcard impact on palindrome checks

   Wildcards '?' can match any character, so palindrome checks must be adapted to treat '?' as a match with any character.

2. Step 2: Adapt DP palindrome center expansion

   Modify the center expansion condition to allow s[left] == s[right] or either is '?', preserving O(n^2) time and DP structure.

3. Step 3: Evaluate other options

   Precomputing ignoring '?' is incorrect as it misses wildcard matches. Pure recursion is inefficient. Replacing '?' with all characters is exponential and impractical.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Adapting palindrome checks for '?' preserves DP correctness and efficiency [OK]

Hint: Adapt palindrome checks, keep DP structure for wildcards [OK]

Common Mistakes:

• Ignoring wildcard impact on palindrome checks
• Trying exponential brute force over all replacements
• Assuming DP cannot handle wildcards

5. Suppose the wildcard pattern matching problem is extended so that the '*' wildcard can match any sequence of characters, but now the input string can be infinitely long (streaming input). Which modification to the DP approach is necessary to handle this scenario efficiently?

hard

A. Switch to a greedy two-pointer approach that backtracks on '*' positions to avoid DP overhead

B. Use recursion with memoization caching all substring pairs to handle infinite input

C. Precompute all possible matches for '*' in advance and store in a lookup table

D. Use the same space-optimized DP with arrays sized by pattern length, processing input character by character

Solution

1. Step 1: Understand infinite input constraints

   DP requires O(m*n) time and space, not feasible for infinite input length.

2. Step 2: Identify suitable approach

   Greedy two-pointer with backtracking on '*' positions can process streaming input efficiently without full DP table.

3. Step 3: Why other options fail

   Precomputing or recursion with memoization is impossible with infinite input; DP arrays cannot grow infinitely.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Greedy with backtracking handles streaming input efficiently [OK]

Hint: Infinite input forbids DP; greedy with backtracking is needed [OK]

Common Mistakes:

• Trying DP on infinite input
• Assuming memoization works with infinite data
• Ignoring streaming constraints