Understanding Palindromes: Brute Force vs Expand Around Center Algorithms | Optimizing Time Complexity | n^3 vs n^2

The algorithm discussed in this thread expand around center approach is a powerful technique that can solve a variety of problems related to palindromes and string manipulation. It’s also an important concept in real-world applications, especially in fields like data processing, bioinformatics, and text analysis. Let’s why?

Why is This Important in the Real World?

📌 Google – Search, NLP, and Plagiarism Detection

🔹 Problem:

Google needs to analyze millions of documents for plagiarism, text similarity, and search ranking.

🔹 Why this matters?

• A copied article often has mirrored sentences.
• Palindromic structures in text help detect rephrased or plagiarized content.
• NLP models (like Google Translate) need to recognize symmetric structures in different languages.

✅ Where Expand Around Center is used?

1. Google uses palindromic pattern detection to:
2. Detect mirrored or reversed phrases in plagiarism detection.
3. Optimize auto-suggestions in search queries.
4. Improve spell-check and text similarity analysis.

Situation:

Given a string s, return the longest substring of s that is a palindrome.

A palindrome is a string that reads the same forward and backward.

If there are multiple palindromic substrings that have the same length, return any one of them.

Example 1:

Input: s = "ababd"
Output: "bab"

Action:

isPalindrome(word) {
    let l = 0, r = word.length - 1
    while (l < r) {
        if (word[l] !== word[r]) {
            return false
        }
        l++
        r--
    }
    return true
}

longestPalindrome(s) {
    if (s.length === 1) {
        return s
    }
    let result = ""
    for (let i = 0; i < s.length; i++) {
        for (let j = i + 1; j <= s.length; j++) {
            let substring = s.substring(i, j)
            if (this.isPalindrome(substring)) {
                if (result.length < substring.length) {
                    result = substring
                }
            }
        }
    }
    return result
}

Brute-Force Approach : How it works:

1. Generate all possible substrings of the string.
2. For each substring, check if it is a palindrome using the isPalindrome function.
3. Keep track of the longest palindrome found.

Result:

1. Time Complexity:
2. Nested for loops takes O(N²) time.
3. isPalindrome, for a substring of length k, this function takes O(k) time.
4. The length of the substring (k) can vary from 1 to N (the length of the entire string), In the worst case, k = N.
5. Checking if a substring is a palindrome takes O(N) time in the worst case.
6. Overall time complexity: O(N³).
7. Space Complexity:
8. O(1) (no extra space is used apart from storing the result).

Why it’s inefficient:

1. It checks every possible substring, even those that cannot possibly be palindromes.
2. The isPalindrome function is called repeatedly for overlapping substrings, leading to redundant work.

Now let's see how we can optimize it:

Expand Around Center Approach

How it works:

1. Treat each character (or pair of characters) as the center of a potential palindrome.
2. Expand outwards from the center as long as the characters on both sides are the same.
3. Keep track of the longest palindrome found.

1. Time Complexity:
2. There are 2N-1 possible centers (each character and each pair of characters).
3. For each center, expanding takes O(N) time in the worst case.
4. Overall time complexity: O(N²).
5. Space Complexity: O(1) (no extra space is used apart from storing the result).

Why it’s efficient:

1. It avoids checking all possible substrings and focuses only on potential palindromic centers.
2. It eliminates redundant work by expanding only when necessary.

Let's use the string s = "babad".

We want to find the longest palindromic substring in this string.

var longestPalindrome = function (s) {
let start = 0
let maxLength = 1

This function takes two indices, left and right, and expands outwards as long as the characters at these indices are the same and the indices are within the bounds of the string.

If the current substring length (right - left + 1) is greater than maxLength, it updates maxLength and start.

function expandAroundCenter(left, right) {

 while (0 <= left && right < s.length 
    && s[left] === s[right]) {
  
  const current = right - left + 1

  if (maxLength < current) {
    maxLength = current
    start = left
  }

  left--
  right++
 }

}

for (let i = 0; i < s.length; i++) {
 expandAroundCenter(i, i)
 expandAroundCenter(i, i + 1)
}

 return s.substring(start, start + maxLength)
};

How this works?

Visualizing

s = "babad".

Odd-Length Palindromes (center is a single character):

i = 0 (character = 'b'):
Left = 0, Right = 0
Expand: s[0] == s[0] → 'b' == 'b' → Palindrome ("b")
Update maxLength = 1, start = 0
Expand further: Left = -1 (out of bounds) → Stop

next iteration

i = 1 (character = 'a'):
Left = 1, Right = 1
Expand: s[1] == s[1] → 'a' == 'a' → Palindrome ("a")

Update maxLength = 1, start = 1

Expand further: Left = 0, Right = 2 → s[0] == s[2] → 'b' == 'b' → Palindrome ("bab")
Update maxLength = 3, start = 0
Expand further: Left = -1 (out of bounds) → Stop

next iteration

i = 2 (character = 'b'):
Left = 2, Right = 2
Expand: s[2] == s[2] → 'b' == 'b' → Palindrome ("b")

maxLength remains 3
Expand further: Left = 1, Right = 3 → s[1] == s[3] → 'a' == 'a' → Palindrome ("aba")

Update maxLength = 3, start = 1
Expand further: Left = 0, Right = 4 → s[0] == s[4] → 'b' == 'd' → Not a palindrome → Stop

i = 3 (character = 'a'):
Left = 3, Right = 3

Expand: s[3] == s[3] → 'a' == 'a' → Palindrome ("a")
maxLength remains 3

Expand further: Left = 2, Right = 4 → s[2] == s[4] → 'b' == 'd' → Not a palindrome → Stop

i = 4 (character = 'd'):
Left = 4, Right = 4
Expand: s[4] == s[4] → 'd' == 'd' → Palindrome ("d")
maxLength remains 3
Expand further: Left = 3, Right = 5 (out of bounds) → Stop

Another Example: s = "abba", (Even-Length):

Step 1: Initialize Variables

start = 0

maxLength = 1

Step 2: Loop Through the String

i = 0 (characters = 'a' and 'b'):
Left = 0, Right = 1
Check if s[0] == s[1] → 'a' == 'b' → Not a palindrome → Stop

i = 1 (characters = 'b' and 'b'):
Left = 1, Right = 2

Check if s[1] == s[2] → 'b' == 'b' → Palindrome ("bb")
Update maxLength = 2, start = 1

Expand further: Left = 0, Right = 3 → s[0] == s[3] → 'a' == 'a' → Palindrome ("abba")

Update maxLength = 4, start = 0
Expand further: Left = -1 (out of bounds) → Stop

i = 2 (characters = 'b' and 'a'):
Left = 2, Right = 3
Check if s[2] == s[3] → 'b' == 'a' → Not a palindrome → Stop

Step 3: Final Result
The longest palindrome found is "abba", with a length of 4.
The function returns s.substring(start, start + maxLength), which is s.substring(0, 4) → "abba".

Use the expand-around-center approach for finding the longest palindromic substring because it is more efficient and scales better for larger inputs. The brute-force approach is only useful for understanding the problem or for very small strings.

If the input size is around 100k length, see how much difference it makes with brute force approach vs expand around center optimized one.

Other Problems This Approach Can Solve:

1. Longest Palindromic Substring:
2. Find the longest substring in a string that is a palindrome.
3. Example: For babad, the longest palindromic substring is bab or aba.
4. Count All Palindromic Substrings:
5. Count the number of substrings in a string that are palindromes.
6. Example: For abc, the count is 3 ("a", "b", "c").
7. Longest Palindromic Subsequence:
8. Find the longest subsequence (not necessarily contiguous) that is a palindrome.
9. Example: For bbbab, the longest palindromic subsequence is bbbb.
10. Check if a String is a Palindrome:
11. Determine if the entire string is a palindrome.
12. Example: madam is a palindrome, but "hello" is not.
13. Find All Distinct Palindromic Substrings:
14. Return all unique palindromic substrings in a string.
15. Example: For aabaa, the distinct palindromic substrings are ["a", "aa", "aabaa", "aba", "b"].
16. Minimum Insertions to Make a String Palindrome:
17. Find the minimum number of insertions required to make a string a palindrome.
18. Example: For abca, the minimum insertions required is 1 (insert 'b' to make "abcba").

#palindrome #leetcode #expandAroundCenter