Expand from Center Algorithm — DP Pattern — Palindrome

DP Pattern

While exploring coding patterns for most asked questions in FAANG interviews, I came across this pattern being used in two of the Blind 75 problems. So, here is the article explaining about the pattern and usage in problems.

About Expand from Center Algorithm:

The “expand from center” algorithm is a technique used to solve problems related to palindromic strings, such as finding the longest palindromic substring or the number of palindromic substrings in a given string.

This methodology relies on the property of palindromes, which exhibit symmetry around the center. The algorithm takes a string and, for each character or pair of characters in the string, tries to expand on both sides to find a palindrome.

This expansion continues as long as the characters on both sides are equal and within the boundaries of the string. The length of the palindrome or the number of palindromic substrings is determined based on the extent of expansion.

The “expand from center” algorithm is a more efficient way to solve these problems as it avoids unnecessary re-computation, thus reducing the time complexity significantly.

Let’s implement this algorithm in two of the most repeatedly asked interview coding questions.

1. Longest Palindromic Substring
2. Palindromic Substrings

1. Longest Palindromic Substring:

Given a string s, return the longest palindromic substring in s.

Example 1:

Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.

Example 2:

Input: s = "cbbd"
Output: "bb"

https://leetcode.com/problems/longest-palindromic-substring/

Pseudocode:

Function longestPalindrome(s: string)
  if s is null or s length is less than 1 then
    return empty string
  end if

  Initialize start and end as 0

  for i from 0 to length of s do
    len1 ← expandAroundCenter(s, i, i) // assuming odd length
    len2 ← expandAroundCenter(s, i, i + 1) // assuming even length

    len ← maximum of len1 and len2

    if len is greater than (end - start) then
      start ← i - (len - 1) / 2
      end ← i + len / 2
    end if
  end for

  return substring of s from start to end + 1
End Function

Function expandAroundCenter(s: string, left: int, right: int)
  L ← left, R ← right

  while L is greater than or equal to 0 and R is less than s length and character at L in s is equal to character at R in s do
    decrement L
    increment R
  end while

  return R - L - 1
End Function

Algorithm

1. Start with checking if the provided string s is null or its length is less than 1. If true, return an empty string as there can't be any palindrome.
2. Initialize start and end variables to 0. They will represent the start and end indices of the longest palindromic substring.
3. Loop over the string s with a variable i.
4. Inside the loop, for each i, calculate two lengths - len1 and len2. len1 is the length of the palindrome assuming the length is odd (i.e., palindrome is expanding around a single character), and len2 is the length of the palindrome assuming the length is even (i.e., palindrome is expanding around a pair of characters).
5. Find the maximum value between len1 and len2 and assign it to len.
6. If len is greater than the current end - start, update start and end to represent the new longest palindromic substring.
7. Continue this process for all characters in the string.
8. Finally, return the longest palindromic substring from s using the start and end indices.

Note: expandAroundCenter function is used to find the length of the palindrome by expanding around the center (single character or a pair of characters) and checks for characters equality going outwards.

Java Solution:

public class Solution {
    public String longestPalindrome(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); // assuming odd length
            int len2 = expandAroundCenter(s, i, i + 1); // assuming even length
            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 int expandAroundCenter(String s, int left, int right) {
        int L = left, R = right;
        while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) {
            L--;
            R++;
        }
        return R - L - 1;
    }
}

2. Palindromic Substrings:

Given a string s, return the number of palindromic substrings in it.

A string is a palindrome when it reads the same backward as forward.

A substring is a contiguous sequence of characters within the string.

Example 1:

Input: s = "abc"
Output: 3
Explanation: Three palindromic strings: "a", "b", "c".

Example 2:

Input: s = "aaa"
Output: 6
Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".

https://leetcode.com/problems/palindromic-substrings/

Pseudocode:

Function countSubstrings(s: string)
  Initialize count as 0

  for i from 0 to length of s do
    count ← count + expandAroundCenter(s, i, i) // assuming odd length
    count ← count + expandAroundCenter(s, i, i + 1) // assuming even length
  end for

  return count
End Function

Function expandAroundCenter(s: string, left: int, right: int)
  L ← left, R ← right

  while L is greater than or equal to 0 and R is less than s length and character at L in s is equal to character at R in s do
    decrement L
    increment R
  end while

  return (R - L) / 2
End Function

Algorithm:

1. Initialize a count variable to 0. This will hold the count of palindrome substrings.
2. Loop over the string s with a variable i.
3. Inside the loop, for each i, calculate two counts - count1 and count2. count1 is the count of palindrome substrings assuming the length is odd (i.e., palindrome is expanding around a single character), and count2 is the count of palindrome substrings assuming the length is even (i.e., palindrome is expanding around a pair of characters).
4. Add both count1 and count2 to the count variable.
5. Continue this process for all characters in the string.
6. Finally, return count as the total number of palindrome substrings.

Note: expandAroundCenter function is used to find the count of palindrome substrings by expanding around the center (single character or a pair of characters) and checks for characters equality going outwards.

Java Solution:

public class Solution {
    public int countSubstrings(String s) {
        int count = 0;
        for (int i = 0; i < s.length(); i++) {
            count += expandAroundCenter(s, i, i); // assuming odd length
            count += expandAroundCenter(s, i, i + 1); // assuming even length
        }
        return count;
    }

    private int expandAroundCenter(String s, int left, int right) {
        int L = left, R = right;
        while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) {
            L--;
            R++;
        }
        return (R - L) / 2;
    }
}

Thanks for reading📖! I hope you enjoyed😀 reading this article.

You can subscribe here for regular articles😇.

Keep smiling😁!

Have a nice day!