Longest Palindromic Substring in DSA Typescript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of expanding around center approach

What is the output of the following TypeScript code that finds the longest palindromic substring by expanding around each center?

DSA Typescript

function longestPalindrome(s: string): string {
  if (s.length < 1) return "";
  let start = 0, end = 0;

  function expandAroundCenter(left: number, right: number): number {
    while (left >= 0 && right < s.length && s[left] === s[right]) {
      left--;
      right++;
    }
    return right - left - 1;
  }

  for (let i = 0; i < s.length; i++) {
    const len1 = expandAroundCenter(i, i);
    const len2 = expandAroundCenter(i, i + 1);
    const len = Math.max(len1, len2);
    if (len > end - start + 1) {
      start = i - Math.floor((len - 1) / 2);
      end = i + Math.floor(len / 2);
    }
  }
  return s.substring(start, end + 1);
}

console.log(longestPalindrome("babad"));

A "bab"

B "aba"

C "babad"

D "bad"

💡 Hint

The function expands around each character and between characters to find palindromes. It returns the first longest palindrome found.

The code expands around each center and finds "bab" and "aba" as palindromes of length 3. Since "bab" is found first, it returns "bab".

🧠 Conceptual

intermediate

Understanding palindrome expansion boundaries

In the expandAroundCenter function, why do we return right - left - 1 as the length of the palindrome?

A Because the palindrome length is always right minus left without adjustment

B Because right and left represent the exact palindrome boundaries after the loop

C Because the function counts characters twice and needs correction

D Because left and right are incremented one step beyond the palindrome boundaries in the last loop iteration

💡 Hint

Think about what happens to left and right pointers when the while loop stops.

The while loop stops when s[left] !== s[right] or boundaries are exceeded, so left and right have moved one step beyond the palindrome. Subtracting 1 corrects the length.

🔧 Debug

advanced

Identify the error in this palindrome substring code

What error will this TypeScript code produce when run, and why?

DSA Typescript

function longestPalindrome(s: string): string {
  let start = 0, maxLength = 1;

  for (let i = 0; i < s.length; i++) {
    for (let j = i; j < s.length; j++) {
      let flag = true;
      for (let k = 0; k < (j - i + 1) / 2; k++) {
        if (s[i + k] !== s[j - k]) {
          flag = false;
          break;
        }
      }
      if (flag && (j - i + 1) > maxLength) {
        start = i;
        maxLength = j - i + 1;
      }
    }
  }
  return s.substring(start, start + maxLength);
}

console.log(longestPalindrome("cbbd"));

A No error; output is "bb"

B TypeError due to invalid substring indices

C SyntaxError because of missing semicolons

D Infinite loop because inner loops never end

💡 Hint

Check the substring indices and loop conditions carefully.

The code correctly checks all substrings and updates the longest palindrome found. It outputs "bb" for input "cbbd" without errors.

❓ Predict Output

advanced

Output of Manacher's algorithm partial implementation

What is the output of this TypeScript code snippet implementing Manacher's algorithm partial step for input "abacdfgdcaba"?

DSA Typescript

function preprocess(s: string): string {
  let t = "^";
  for (let c of s) {
    t += "#" + c;
  }
  t += "#$";
  return t;
}

const s = "abacdfgdcaba";
const t = preprocess(s);
console.log(t);

A "#^a#b#a#c#d#f#g#d#c#a#b#a#$"

B "^#a#b#a#c#d#f#g#d#c#a#b#a#$"

C "^a#b#a#c#d#f#g#d#c#a#b#a#$"

D "^#abacdfgdcaba#$"

💡 Hint

Manacher's algorithm inserts '#' between characters and adds '^' and '$' at ends.

The preprocess function adds '^' at start, '#' before each character, and '$' at end, producing "^#a#b#a#c#d#f#g#d#c#a#b#a#$".

🧠 Conceptual

expert

Time complexity of longest palindromic substring algorithms

Which statement correctly describes the time complexity of the common algorithms for finding the longest palindromic substring?

A Expanding around center runs in O(n), Manacher's algorithm runs in O(n^2)

B Both expanding around center and Manacher's algorithm run in O(n^3)

C Expanding around center approach runs in O(n^2), Manacher's algorithm runs in O(n)

D Both algorithms run in O(n log n)

💡 Hint

Consider how many centers are expanded and how Manacher's algorithm optimizes.

Expanding around center checks up to 2n centers with expansions up to n, resulting in O(n^2). Manacher's algorithm uses clever preprocessing and tracking to achieve O(n).

Practice

1. What is the main goal of the Longest Palindromic Substring problem?

easy

A. Find the longest substring with all unique characters

B. Find the longest substring that reads the same forwards and backwards

C. Find the longest substring with increasing characters

D. Find the longest substring that contains only vowels

Solution

1. Step 1: Understand palindrome definition

   A palindrome reads the same forwards and backwards, like 'madam' or 'racecar'.

2. Step 2: Identify the problem goal

   The problem asks to find the longest substring inside a string that is a palindrome.

3. Final Answer:

   Find the longest substring that reads the same forwards and backwards -> Option B

4. Quick Check:

   Palindrome substring = longest palindrome [OK]

Hint: Look for substrings that mirror around a center [OK]

Common Mistakes:

• Confusing palindrome with unique characters
• Looking for longest substring without repeats
• Thinking about substrings with vowels only

2. Which of the following TypeScript function signatures correctly represents a function to find the longest palindromic substring?

easy

A. function longestPalindrome(s: string): string

B. function longestPalindrome(s: number): number

C. function longestPalindrome(s: string): number[]

D. function longestPalindrome(s: boolean): string

Solution

1. Step 1: Check input parameter type

   The input is a string, so parameter type must be string.

2. Step 2: Check return type

   The function returns the longest palindromic substring, which is a string.

3. Final Answer:

   function longestPalindrome(s: string): string -> Option A

4. Quick Check:

   Input string, output string [OK]

Hint: Input and output are both strings for this problem [OK]

Common Mistakes:

• Using wrong input type like number or boolean
• Returning array instead of string
• Mixing input and output types

3. What will be the output of the following TypeScript code?

function longestPalindrome(s: string): string {
  let start = 0, maxLength = 1;
  for (let i = 0; i < s.length; i++) {
    let low = i, high = i;
    while (low >= 0 && high < s.length && s[low] === s[high]) {
      if (high - low + 1 > maxLength) {
        start = low;
        maxLength = high - low + 1;
      }
      low--;
      high++;
    }
  }
  return s.substring(start, start + maxLength);
}

console.log(longestPalindrome('babad'))

medium

A. "bab"

B. "aba"

C. "bad"

D. "babad"

Solution

1. Step 1: Understand the code logic

   The code expands around each character to find odd-length palindromes and tracks the longest one.

2. Step 2: Trace the input 'babad'

   Expanding around index 1 ('a') finds 'bab' (length 3). Around index 2 ('b') finds 'aba' (length 3). Both have length 3, but 'bab' is found first and stored.

3. Final Answer:

   "bab" -> Option A

4. Quick Check:

   First longest palindrome found = "bab" [OK]

Hint: Expand around center and pick first longest palindrome [OK]

Common Mistakes:

• Assuming 'aba' is always returned instead of 'bab'
• Returning entire string incorrectly
• Confusing substring indices

4. Identify the bug in the following TypeScript code for finding the longest palindromic substring:

function longestPalindrome(s: string): string {
  let start = 0, maxLength = 1;
  for (let i = 0; i < s.length; i++) {
    let low = i, high = i + 1;
    while (low >= 0 && high < s.length && s[low] === s[high]) {
      if (high - low + 1 > maxLength) {
        start = low;
        maxLength = high - low + 1;
      }
      low--;
      high++;
    }
  }
  return s.substring(start, start + maxLength);
}

medium

A. The loop should start from 1 instead of 0

B. The substring indices are incorrect in the return statement

C. The code only checks even-length palindromes, missing odd-length ones

D. The variables low and high are initialized incorrectly for odd-length palindromes

Solution

1. Step 1: Analyze initialization of low and high

   low = i and high = i + 1 means it only checks even-length palindromes centered between i and i+1.

2. Step 2: Identify missing odd-length palindrome check

   Odd-length palindromes centered at i (low = high = i) are not checked, so some palindromes are missed.

3. Final Answer:

   The code only checks even-length palindromes, missing odd-length ones -> Option C

4. Quick Check:

   Only even-length palindrome check = bug [OK]

Hint: Check both odd (low=high=i) and even (low=i, high=i+1) centers [OK]

Common Mistakes:

• Checking only even-length palindromes
• Not expanding around single character centers
• Incorrect loop start index

5. Given the string "forgeeksskeegfor", which approach correctly finds the longest palindromic substring and what is that substring?

hard

A. Manacher's algorithm; longest palindrome is "forgeeksskeegfor"

B. Dynamic programming approach; longest palindrome is "forgeeksskeegfor"

C. Brute force checking all substrings; longest palindrome is "ss"

D. Expand around center approach; longest palindrome is "geeksskeeg"

Solution

1. Step 1: Identify the longest palindrome in the string

   The substring "geeksskeeg" is the longest palindrome inside "forgeeksskeegfor".

2. Step 2: Match approach with correct palindrome

   Expand around center approach finds "geeksskeeg" correctly. The entire string is not a palindrome, so options A and B are incorrect. Brute force (C) incorrectly identifies "ss" as the longest.

3. Final Answer:

   Expand around center approach; longest palindrome is "geeksskeeg" -> Option D

4. Quick Check:

   Center expansion finds "geeksskeeg" [OK]

Hint: Use center expansion for efficient palindrome search [OK]

Common Mistakes:

• Assuming entire string is palindrome
• Confusing brute force with efficient methods
• Mixing up palindrome substrings