[AlgoMastery]
Topics›String›Palindrome Substrings
📖

Palindrome Substrings

String
~20 min read
5 practice problems

Overview

Palindrome substrings are substrings that read the same forward and backward (e.g., "aba", "racecar", "a"). Problems involving palindromes are common in coding interviews and test your understanding of two pointers, dynamic programming, and string manipulation.

Common palindrome problems include:

  • Check if a string is a palindrome
  • Find the longest palindromic substring
  • Count all palindromic substrings
  • Valid palindrome with constraints
  • Palindrome partitioning
  • Shortest palindrome

Pattern 1: Check if String is Palindrome

Determine if a string reads the same forward and backward.

Approach: Use two pointers from both ends.

function isPalindrome(s: string): boolean {
  let left = 0;
  let right = s.length - 1;
  
  while (left < right) {
    if (s[left] !== s[right]) {
      return false;
    }
    left++;
    right--;
  }
  
  return true;
}

With constraints (ignore non-alphanumeric, case-insensitive):

function isPalindromeConstrained(s: string): boolean {
  let left = 0;
  let right = s.length - 1;
  
  while (left < right) {
    // Skip non-alphanumeric
    while (left < right && !/[a-zA-Z0-9]/.test(s[left])) {
      left++;
    }
    while (left < right && !/[a-zA-Z0-9]/.test(s[right])) {
      right--;
    }
    
    if (s[left].toLowerCase() !== s[right].toLowerCase()) {
      return false;
    }
    
    left++;
    right--;
  }
  
  return true;
}

Time: O(n), Space: O(1)

Pattern 2: Longest Palindromic Substring

Find the longest substring that is a palindrome.

Approach 1: Expand Around Center

For each position, expand outward while characters match.

function longestPalindrome(s: string): string {
  if (s.length === 0) return "";
  
  let start = 0;
  let maxLen = 1;
  
  function expandAroundCenter(left: number, right: number) {
    while (left >= 0 && right < s.length && s[left] === s[right]) {
      left--;
      right++;
    }
    const len = right - left - 1;
    if (len > maxLen) {
      maxLen = len;
      start = left + 1;
    }
  }
  
  for (let i = 0; i < s.length; i++) {
    expandAroundCenter(i, i);     // Odd length palindromes
    expandAroundCenter(i, i + 1); // Even length palindromes
  }
  
  return s.substring(start, start + maxLen);
}

Time: O(n²), Space: O(1)

Approach 2: Dynamic Programming

function longestPalindromeDP(s: string): string {
  const n = s.length;
  if (n === 0) return "";
  
  const dp: boolean[][] = Array(n).fill(null).map(() => Array(n).fill(false));
  let start = 0;
  let maxLen = 1;
  
  // Single characters are palindromes
  for (let i = 0; i < n; i++) {
    dp[i][i] = true;
  }
  
  // Check for length 2
  for (let i = 0; i < n - 1; i++) {
    if (s[i] === s[i + 1]) {
      dp[i][i + 1] = true;
      start = i;
      maxLen = 2;
    }
  }
  
  // Check for length 3 and more
  for (let len = 3; len <= n; len++) {
    for (let i = 0; i < n - len + 1; i++) {
      const j = i + len - 1;
      if (s[i] === s[j] && dp[i + 1][j - 1]) {
        dp[i][j] = true;
        start = i;
        maxLen = len;
      }
    }
  }
  
  return s.substring(start, start + maxLen);
}

Time: O(n²), Space: O(n²)

Pattern 3: Count Palindromic Substrings

Count how many palindromic substrings exist in a string.

Approach: Expand around center for each position.

function countSubstrings(s: string): number {
  let count = 0;
  
  function expandAroundCenter(left: number, right: number) {
    while (left >= 0 && right < s.length && s[left] === s[right]) {
      count++;
      left--;
      right++;
    }
  }
  
  for (let i = 0; i < s.length; i++) {
    expandAroundCenter(i, i);     // Odd length
    expandAroundCenter(i, i + 1); // Even length
  }
  
  return count;
}

DP approach:

function countSubstringsDP(s: string): number {
  const n = s.length;
  const dp: boolean[][] = Array(n).fill(null).map(() => Array(n).fill(false));
  let count = 0;
  
  // Single characters
  for (let i = 0; i < n; i++) {
    dp[i][i] = true;
    count++;
  }
  
  // Length 2
  for (let i = 0; i < n - 1; i++) {
    if (s[i] === s[i + 1]) {
      dp[i][i + 1] = true;
      count++;
    }
  }
  
  // Length 3+
  for (let len = 3; len <= n; len++) {
    for (let i = 0; i < n - len + 1; i++) {
      const j = i + len - 1;
      if (s[i] === s[j] && dp[i + 1][j - 1]) {
        dp[i][j] = true;
        count++;
      }
    }
  }
  
  return count;
}

Time: O(n²), Space: O(n²) for DP, O(1) for expand-around-center

Pattern 4: Valid Palindrome (After Deletion)

Check if a string can be a palindrome after deleting at most K characters.

function validPalindrome(s: string, k: number = 1): boolean {
  function isPalindromeRange(left: number, right: number): boolean {
    while (left < right) {
      if (s[left] !== s[right]) return false;
      left++;
      right--;
    }
    return true;
  }
  
  function canBePalindrome(left: number, right: number, deletes: number): boolean {
    if (left >= right) return true;
    if (deletes < 0) return false;
    
    if (s[left] === s[right]) {
      return canBePalindrome(left + 1, right - 1, deletes);
    } else {
      return canBePalindrome(left + 1, right, deletes - 1) ||
             canBePalindrome(left, right - 1, deletes - 1);
    }
  }
  
  return canBePalindrome(0, s.length - 1, k);
}

Optimized with memoization:

function validPalindromeMemo(s: string, k: number): boolean {
  const memo = new Map<string, boolean>();
  
  function canBePalindrome(left: number, right: number, deletes: number): boolean {
    if (left >= right) return true;
    if (deletes < 0) return false;
    
    const key = `${left}-${right}-${deletes}`;
    if (memo.has(key)) return memo.get(key)!;
    
    let result: boolean;
    if (s[left] === s[right]) {
      result = canBePalindrome(left + 1, right - 1, deletes);
    } else {
      result = canBePalindrome(left + 1, right, deletes - 1) ||
               canBePalindrome(left, right - 1, deletes - 1);
    }
    
    memo.set(key, result);
    return result;
  }
  
  return canBePalindrome(0, s.length - 1, k);
}

Time: O(n k), Space: O(n k)

Pattern 5: Palindrome Partitioning

Partition a string such that every substring is a palindrome.

Find all possible partitions:

function partition(s: string): string[][] {
  const result: string[][] = [];
  const current: string[] = [];
  
  function isPalindrome(str: string): boolean {
    let left = 0, right = str.length - 1;
    while (left < right) {
      if (str[left] !== str[right]) return false;
      left++;
      right--;
    }
    return true;
  }
  
  function backtrack(start: number) {
    if (start === s.length) {
      result.push([...current]);
      return;
    }
    
    for (let end = start + 1; end <= s.length; end++) {
      const substr = s.substring(start, end);
      if (isPalindrome(substr)) {
        current.push(substr);
        backtrack(end);
        current.pop();
      }
    }
  }
  
  backtrack(0);
  return result;
}

Optimized with DP for palindrome checking:

function partitionOptimized(s: string): string[][] {
  const n = s.length;
  const dp: boolean[][] = Array(n).fill(null).map(() => Array(n).fill(false));
  const result: string[][] = [];
  
  // Build palindrome DP table
  for (let i = 0; i < n; i++) {
    dp[i][i] = true;
  }
  for (let i = 0; i < n - 1; i++) {
    dp[i][i + 1] = s[i] === s[i + 1];
  }
  for (let len = 3; len <= n; len++) {
    for (let i = 0; i < n - len + 1; i++) {
      const j = i + len - 1;
      dp[i][j] = s[i] === s[j] && dp[i + 1][j - 1];
    }
  }
  
  function backtrack(start: number, current: string[]) {
    if (start === n) {
      result.push([...current]);
      return;
    }
    
    for (let end = start; end < n; end++) {
      if (dp[start][end]) {
        current.push(s.substring(start, end + 1));
        backtrack(end + 1, current);
        current.pop();
      }
    }
  }
  
  backtrack(0, []);
  return result;
}

Time: O(2^n) worst case, Space: O(n²) for DP table

Pattern 6: Shortest Palindrome

Find the shortest palindrome by adding characters to the beginning.

Approach: Find the longest palindromic prefix, then reverse the remaining suffix.

function shortestPalindrome(s: string): string {
  if (s.length === 0) return "";
  
  // Find longest palindromic prefix
  let i = 0;
  for (let j = s.length - 1; j >= 0; j--) {
    if (s[i] === s[j]) {
      i++;
    }
  }
  
  // If entire string is palindrome
  if (i === s.length) return s;
  
  // Reverse the remaining suffix and prepend
  const suffix = s.substring(i);
  const reversed = suffix.split('').reverse().join('');
  return reversed + shortestPalindrome(s.substring(0, i)) + suffix;
}

Optimized with KMP:

function shortestPalindromeKMP(s: string): string {
  const reversed = s.split('').reverse().join('');
  const combined = s + '#' + reversed;
  const lps = buildLPS(combined);
  const longestPalindromicPrefix = lps[combined.length - 1];
  const suffix = s.substring(longestPalindromicPrefix);
  return suffix.split('').reverse().join('') + s;
}

function buildLPS(pattern: string): number[] {
  const m = pattern.length;
  const lps = new Array(m).fill(0);
  let len = 0;
  let i = 1;
  
  while (i < m) {
    if (pattern[i] === pattern[len]) {
      len++;
      lps[i] = len;
      i++;
    } else {
      if (len !== 0) {
        len = lps[len - 1];
      } else {
        lps[i] = 0;
        i++;
      }
    }
  }
  
  return lps;
}

Time: O(n), Space: O(n)

Common Variations

Variation 1: Check if Palindrome Can Be Formed

Check if characters can be rearranged to form a palindrome.

function canFormPalindrome(s: string): boolean {
  const freq = new Map<string, number>();
  
  for (const char of s) {
    freq.set(char, (freq.get(char) || 0) + 1);
  }
  
  let oddCount = 0;
  for (const count of freq.values()) {
    if (count % 2 === 1) {
      oddCount++;
    }
  }
  
  // Palindrome can have at most one character with odd frequency
  return oddCount <= 1;
}

Variation 2: Longest Palindromic Subsequence

Find longest subsequence (not substring) that is a palindrome.

function longestPalindromeSubseq(s: string): number {
  const n = s.length;
  const dp: number[][] = Array(n).fill(null).map(() => Array(n).fill(0));
  
  // Single characters
  for (let i = 0; i < n; i++) {
    dp[i][i] = 1;
  }
  
  for (let len = 2; len <= n; len++) {
    for (let i = 0; i < n - len + 1; i++) {
      const j = i + len - 1;
      if (s[i] === s[j]) {
        dp[i][j] = 2 + dp[i + 1][j - 1];
      } else {
        dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
      }
    }
  }
  
  return dp[0][n - 1];
}

Time: O(n²), Space: O(n²)

When to Use These Patterns

Use palindrome techniques when:

  • Problem asks about "palindrome" or "symmetric" strings
  • Need to check if string reads same forward/backward
  • Finding longest or shortest palindromic substring
  • Partitioning string into palindromic parts
  • Counting palindromic substrings

Template (Expand Around Center)

function palindromeTemplate(s: string): number {
  let result = 0;
  
  function expand(left: number, right: number) {
    while (left >= 0 && right < s.length && s[left] === s[right]) {
      // Process palindrome
      left--;
      right++;
    }
    // Update result
  }
  
  for (let i = 0; i < s.length; i++) {
    expand(i, i);     // Odd length
    expand(i, i + 1); // Even length
  }
  
  return result;
}

Time and Space Complexity Summary

  • Check palindrome: O(n) time, O(1) space
  • Longest palindromic substring (expand): O(n²) time, O(1) space
  • Longest palindromic substring (DP): O(n²) time, O(n²) space
  • Count palindromic substrings: O(n²) time, O(1) or O(n²) space
  • Palindrome partitioning: O(2^n) time worst case, O(n²) space
  • Shortest palindrome: O(n) time with KMP, O(n) space

Practice Tips

  1. Master expand-around-center — Most efficient for substring problems
  2. Understand DP approach — Useful for subsequence and partitioning
  3. Handle even/odd lengths — Always check both cases
  4. Optimize with memoization — For recursive solutions
  5. Use KMP for shortest palindrome — More efficient than naive

Related Concepts

  • Two Pointers — Core technique for palindrome checking
  • Dynamic Programming — Used for subsequence and partitioning
  • String Manipulation — Often combined with string operations
  • KMP Algorithm — Useful for shortest palindrome problem

Palindrome problems are excellent for practicing two pointers and dynamic programming. Master expand-around-center and DP approaches, and you'll be well-prepared for palindrome-related interview questions.

← PreviousSubstring SearchNext →Anagram Problems