Maximal Symmetric Substring

You are in a Google phone screen, and the interviewer gives you a string "babad" and asks you to find the longest substring that reads the same forwards and backwards. You quickly spot "bab" and "aba", but how do you write an algorithm that finds such palindromes efficiently for any input? This problem, known as Longest Palindromic Substring on other platforms, is one of the most frequently asked string manipulation questions at companies like Adobe, Meta, Google, and Amazon. It tests your ability to think about symmetry, two-pointer techniques, and the subtle difference between odd-length and even-length palindromes.

TL;DR

For each index in the string, expand outward from that index as the center of a potential palindrome, checking both odd-length centers (single character) and even-length centers (gap between two characters). Track the longest palindrome found across all expansions. This runs in O(n^2) time and O(1) space. The helper function expandAroundCenter(s, left, right) returns the length of the palindrome found by expanding while characters match. Update start and end indices whenever a longer palindrome is discovered, then return s.substring(start, end + 1).

Why This Problem Matters

Palindromes show up everywhere in string-processing interviews because they combine pattern recognition with pointer manipulation. This particular problem is a gateway to harder variants like palindromic substrings counting, palindrome partitioning, and longest palindromic subsequence. It also surfaces regularly at top companies - Adobe, Meta, and Google all ask it with high frequency. Getting comfortable with the expand-around-center technique gives you a reusable tool for an entire family of palindrome questions.

Palindromes: A Quick Refresher

A palindrome is a string that reads the same forwards and backwards. Single characters are trivially palindromes. Beyond that, palindromes come in two flavors:

• Odd-length: There is a single center character. Examples: "aba" (center b), "racecar" (center e).
• Even-length: The center sits between two characters. Examples: "bb" (center between the two bs), "abba" (center between the two bs).

This distinction is important because any algorithm that only checks one type will miss valid palindromes of the other type.

Understanding the Problem

Given: A string s of alphanumeric characters with 1 <= s.length <= 1000.

Find: The longest substring of s that is a palindrome.

Return: The palindromic substring itself (if there are ties, any valid answer is accepted).

Here is our primary example, the string "babad":

Looking at this string by hand, you can find several palindromes: "b", "a", "bab", "aba", "d". The longest ones are "bab" and "aba", both with length 3. Either answer is valid.

longestPalindrome("babad") => "bab"
longestPalindrome("cbbd")  => "bb"

Edge Cases to Consider

1. Single character: "a" is already a palindrome, return it
2. All identical characters: "aaaa" is itself the longest palindrome
3. Already a palindrome: "racecar" returns the entire string
4. Even-length palindrome at the edges: "cbbd" has "bb" which requires even-center detection

Solution Approach

The brute-force path would be to check every possible substring and test whether it is a palindrome - that gives O(n^3) time. We can do much better by observing that palindromes grow outward from their center. Instead of checking all substrings, we iterate over all possible centers and expand outward from each one.

Why Expand Around Center?

A palindrome mirrors around its center. If you already know that s[left] == s[right], you only need to check the next pair outward: s[left-1] and s[right+1]. This cuts out redundant work compared to checking entire substrings from scratch.

For a string of length n, there are 2n - 1 possible centers: n single-character centers (odd-length palindromes) and n - 1 gap centers (even-length palindromes). For each center, expansion takes O(n) time in the worst case, giving O(n^2) overall.

Tracing Through "babad"

Odd expansion from center i=1 (character 'a'):

Starting at index 1, the character 'a' is trivially a palindrome. Expanding to indices (0, 2), we find s[0]='b' equals s[2]='b', so the palindrome grows to "bab" with length 3. The next expansion would go to index -1, which is out of bounds, so we stop.

Odd expansion from center i=2 (character 'b'):

Starting at index 2, expanding to (1, 3) gives s[1]='a' equals s[3]='a', so the palindrome is "aba" with length 3. The next expansion to (0, 4) finds s[0]='b' does not equal s[4]='d', so expansion stops.

Even expansion from gap between i=1 and i=2:

Not every gap produces a palindrome. Here s[1]='a' does not match s[2]='b', so there is no even-length palindrome centered at this gap.

Even expansion for "cbbd" (where even-length wins):

In "cbbd", the gap between indices 1 and 2 produces the longest palindrome. Both characters are 'b', so the palindrome "bb" has length 2. The next expansion finds 'c' != 'd' and stops.

Full trace summary for "babad":

The algorithm checks every center, keeping track of the longest palindrome seen. Centers at i=1 and i=2 both find palindromes of length 3. Since "bab" is found first, it becomes the result.

Implementation

Prefer a different language? Jump to solutions in other languages.

The algorithm has two parts: a helper function that expands from a given center, and a main loop that tries every center position.

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++) {
      // Check odd-length palindrome centered at i
      int len1 = expandAroundCenter(s, i, i);
      // Check even-length palindrome centered between i and i+1
      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 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;
  }
}

The expandAroundCenter function takes starting left and right indices and pushes them outward as long as the characters at both positions match and both indices are within bounds. When the while loop exits, left and right have each moved one step past the last valid palindrome boundary, so the palindrome length is right - left - 1.

In the main loop, for each index i:

• expandAroundCenter(s, i, i) handles odd-length palindromes (single center character)
• expandAroundCenter(s, i, i + 1) handles even-length palindromes (gap center)

The index formulas start = i - (len - 1) / 2 and end = i + len / 2 work because of integer division truncation. For an odd palindrome of length 3 centered at i=2: start = 2 - 1 = 1, end = 2 + 1 = 3, which correctly gives s[1..3].

Walkthrough with "babad"

Final answer: "bab".

Complexity Analysis

Time Complexity: O(n^2)

The outer loop runs n times. For each iteration, the expansion can visit up to n characters total across both odd and even checks. Worst case happens with strings like "aaaa" where every expansion reaches the string boundaries. This gives O(n) work per center and O(n^2) total.

Space Complexity: O(1)

The algorithm uses only a handful of integer variables (start, end, left, right, len1, len2, len). No arrays, hash maps, or recursive calls are involved. The output substring is created once at the end, but that's the required return value, not auxiliary space.

Alternative Approaches

1. Brute force - Check all O(n^2) substrings, each palindrome check costs O(n). Total: O(n^3) time, O(1) space.
2. Dynamic programming - Build a 2D boolean table where dp[i][j] indicates whether s[i..j] is a palindrome. O(n^2) time and O(n^2) space. Correct but uses more memory than expand-around-center.
3. Manacher's algorithm - Exploits palindrome symmetry to achieve O(n) time and O(n) space. Rarely expected in interviews due to implementation complexity.

The expand-around-center approach hits the sweet spot: O(n^2) time with O(1) space, straightforward to implement, and easy to explain on a whiteboard.

Common Pitfalls

1. Forgetting even-length palindromes: Only checking expandAroundCenter(s, i, i) will miss palindromes like "bb" or "abba". Always check both odd and even centers.

2. Off-by-one in the return length: The expansion loop overshoots by one step in each direction before stopping. The correct length formula is right - left - 1, not right - left + 1.

3. Wrong index formula for start/end: When converting from a palindrome length back to substring indices, the formulas start = i - (len - 1) / 2 and end = i + len / 2 rely on integer division. Getting these wrong leads to returning the wrong substring.

4. Skipping the empty string check: Without the guard if (s == null || s.length() < 1) return "", the algorithm would crash on empty input.

Interview Tips

When solving this in an interview:

1. Start with the brute force: Mention the O(n^3) approach of checking all substrings. This shows you understand the problem before optimizing.

2. Explain the optimization: "Palindromes expand from their center, so instead of checking all substrings, I can expand outward from each of the 2n-1 possible centers."

3. Write the helper first: Implement expandAroundCenter as a standalone function, then build the main loop around it. This modular approach is cleaner and less error-prone.

4. Trace through an example: Walk through "babad" showing how centers at i=1 and i=2 both produce length-3 palindromes.

5. Know your follow-ups: Interviewers commonly ask about Manacher's algorithm (O(n) time), counting all palindromic substrings (modify the helper to count instead of track max), or the DP approach (trade space for a different perspective).

Key Takeaways

• The expand-around-center technique checks all 2n - 1 possible palindrome centers (n odd + n-1 even) in O(n^2) time with O(1) space, making it the standard interview solution for 2026.
• The helper function expandAroundCenter(s, left, right) returns right - left - 1 after the while loop because both pointers overshoot by one position when expansion stops.
• Always check both odd-length (left = right = i) and even-length (left = i, right = i + 1) centers at each index; skipping even-length checks is the most common bug.
• The index formulas start = i - (len - 1) / 2 and end = i + len / 2 use integer division truncation to correctly handle both odd and even palindrome lengths.
• Mention the DP alternative (O(n^2) time, O(n^2) space) and Manacher's algorithm (O(n) time, O(n) space) to show depth of knowledge, but implement expand-around-center for the best time-space tradeoff.

Solutions in Other Languages

Python

class Solution:
    def longest_palindrome(self, s: str) -> str:
        if not s:
            return ""

        start, end = 0, 0

        for i in range(len(s)):
            len1 = self._expand_around_center(s, i, i)
            len2 = self._expand_around_center(s, i, i + 1)
            max_len = max(len1, len2)
            if max_len > end - start:
                start = i - (max_len - 1) // 2
                end = i + max_len // 2

        return s[start:end + 1]

    def _expand_around_center(self, s: str, left: int, right: int) -> int:
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return right - left - 1

Python's integer division with // behaves the same as Java's truncating division for non-negative values, so the index formulas translate directly.

JavaScript

class Solution {
  longestPalindrome(s) {
    if (s.length < 1) return "";

    let start = 0, end = 0;

    const 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++) {
      const len1 = expandAroundCenter(i, i);
      const len2 = expandAroundCenter(i, i + 1);
      const 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);
  }
}

JavaScript does not have integer division, so Math.floor is needed to match the truncation behavior of Java and Python.

TypeScript

class Solution {
  longestPalindrome(s: string): string {
    if (s.length < 1) return "";

    let start = 0, end = 0;

    const 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) {
        start = i - Math.floor((len - 1) / 2);
        end = i + Math.floor(len / 2);
      }
    }

    return s.substring(start, end + 1);
  }
}

C++

#include <string>
#include <algorithm>

class Solution {
public:
  std::string longestPalindrome(std::string &s) {
    if (s.empty()) 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 = std::max(len1, len2);
      if (len > end - start) {
        start = i - (len - 1) / 2;
        end = i + len / 2;
      }
    }

    return s.substr(start, end - start + 1);
  }

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

Note that C++ substr takes a start index and a length, not start and end indices, so the second argument is end - start + 1.

Go

func (sol *Solution) LongestPalindrome(s string) string {
    if len(s) == 0 {
        return ""
    }

    start, end := 0, 0

    for i := 0; i < len(s); i++ {
        len1 := expandAroundCenter(s, i, i)
        len2 := expandAroundCenter(s, i, i+1)
        maxLen := max(len1, len2)
        if maxLen > end-start {
            start = i - (maxLen-1)/2
            end = i + maxLen/2
        }
    }

    return s[start : end+1]
}

func expandAroundCenter(s string, left int, right int) int {
    for left >= 0 && right < len(s) && s[left] == s[right] {
        left--
        right++
    }
    return right - left - 1
}

Go's slice syntax s[start : end+1] is equivalent to Java's s.substring(start, end + 1) since both use exclusive upper bounds.

Kotlin

class Solution {
  fun longestPalindrome(s: String): String {
    if (s.isEmpty()) return ""

    var start = 0
    var end = 0

    for (i in s.indices) {
      val len1 = expandAroundCenter(s, i, i)
      val len2 = expandAroundCenter(s, i, i + 1)
      val len = maxOf(len1, len2)
      if (len > end - start) {
        start = i - (len - 1) / 2
        end = i + len / 2
      }
    }

    return s.substring(start, end + 1)
  }

  private fun expandAroundCenter(s: String, left: Int, right: Int): Int {
    var leftPointer = left
    var rightPointer = right
    while (leftPointer >= 0 && rightPointer < s.length && s[leftPointer] == s[rightPointer]) {
      leftPointer--
      rightPointer++
    }
    return rightPointer - leftPointer - 1
  }
}

Kotlin requires reassigning to mutable var locals since function parameters are val by default.

Scala

class Solution {
  def longestPalindrome(s: String): String = {
    if (s == null || s.length < 1) return ""

    var start = 0
    var end = 0

    for (i <- 0 until s.length) {
      val len1 = expandAroundCenter(s, i, i)
      val len2 = expandAroundCenter(s, i, i + 1)
      val len = Math.max(len1, len2)
      if (len > end - start) {
        start = i - (len - 1) / 2
        end = i + len / 2
      }
    }

    s.substring(start, end + 1)
  }

  private def expandAroundCenter(s: String, left: Int, right: Int): Int = {
    var L = left
    var R = right
    while (L >= 0 && R < s.length && s.charAt(L) == s.charAt(R)) {
      L -= 1
      R += 1
    }
    R - L - 1
  }
}

Ruby

class Solution
  def longest_palindrome(s)
    return '' if s.nil? || s.empty?

    start_idx = 0
    end_idx = 0

    (0...s.length).each do |i|
      len1 = expand_around_center(s, i, i)
      len2 = expand_around_center(s, i, i + 1)
      len = [len1, len2].max
      if len > end_idx - start_idx
        start_idx = i - (len - 1) / 2
        end_idx = i + len / 2
      end
    end

    s[start_idx..end_idx]
  end

  def expand_around_center(s, left, right)
    while left >= 0 && right < s.length && s[left] == s[right]
      left -= 1
      right += 1
    end
    right - left - 1
  end
end

Ruby's inclusive range s[start_idx..end_idx] naturally matches the inclusive end index tracked by the algorithm.

Rust

impl Solution {
    pub fn longest_palindrome(&self, s: String) -> String {
        if s.is_empty() { return String::new(); }

        let chars: Vec<char> = s.chars().collect();
        let mut start = 0i32;
        let mut end = 0i32;

        for i in 0..chars.len() {
            let len1 = self.expand_around_center(&chars, i as i32, i as i32);
            let len2 = self.expand_around_center(&chars, i as i32, (i + 1) as i32);
            let len = len1.max(len2);
            if len > end - start {
                start = i as i32 - (len - 1) / 2;
                end = i as i32 + len / 2;
            }
        }

        chars[start as usize..=end as usize].iter().collect()
    }

    fn expand_around_center(&self, chars: &[char], left: i32, right: i32) -> i32 {
        let mut left = left;
        let mut right = right;
        while left >= 0 && right < chars.len() as i32 && chars[left as usize] == chars[right as usize] {
            left -= 1;
            right += 1;
        }
        right - left - 1
    }
}

Rust requires converting the string to a Vec<char> for O(1) indexing, since Rust strings are UTF-8 encoded and do not support direct index access.

Swift

func longestPalindrome(_ s: String) -> String {
    if s.isEmpty { return "" }

    let chars = Array(s)
    var start = 0
    var end = 0

    for i in 0..<chars.count {
        let len1 = expandAroundCenter(chars, i, i)
        let len2 = expandAroundCenter(chars, i, i + 1)
        let len = max(len1, len2)
        if len > end - start {
            start = i - (len - 1) / 2
            end = i + len / 2
        }
    }

    return String(chars[start...end])
}

private func expandAroundCenter(_ chars: [Character], _ left: Int, _ right: Int) -> Int {
    var leftPointer = left
    var rightPointer = right
    while leftPointer >= 0 && rightPointer < chars.count && chars[leftPointer] == chars[rightPointer] {
        leftPointer -= 1
        rightPointer += 1
    }
    return rightPointer - leftPointer - 1
}

Like Rust, Swift strings are not randomly accessible, so converting to a [Character] array is necessary for efficient index-based access.

Dart

class Solution {
  String longestPalindrome(String s) {
    if (s.isEmpty) 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 = len1 > len2 ? len1 : len2;
      if (len > end - start) {
        start = i - (len - 1) ~/ 2;
        end = i + len ~/ 2;
      }
    }

    return s.substring(start, end + 1);
  }

  int _expandAroundCenter(String s, int left, int right) {
    int leftPointer = left;
    int rightPointer = right;
    while (leftPointer >= 0 && rightPointer < s.length && s[leftPointer] == s[rightPointer]) {
      leftPointer--;
      rightPointer++;
    }
    return rightPointer - leftPointer - 1;
  }
}

Dart uses the ~/ operator for integer division, which is equivalent to Java's / on integers.

C#

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);
            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 - start + 1);
    }

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

C# Substring takes a start index and a length (like C++ substr), so the second argument is end - start + 1.

PHP

class Solution {
    public function longestPalindrome(string $s): string {
        if (strlen($s) < 1) return "";

        $start = 0;
        $end = 0;

        for ($i = 0; $i < strlen($s); $i++) {
            $len1 = $this->expandAroundCenter($s, $i, $i);
            $len2 = $this->expandAroundCenter($s, $i, $i + 1);
            $len = max($len1, $len2);
            if ($len > $end - $start) {
                $start = $i - intdiv($len - 1, 2);
                $end = $i + intdiv($len, 2);
            }
        }

        return substr($s, $start, $end - $start + 1);
    }

    private function expandAroundCenter(string $s, int $left, int $right): int {
        while ($left >= 0 && $right < strlen($s) && $s[$left] === $s[$right]) {
            $left--;
            $right++;
        }
        return $right - $left - 1;
    }
}

PHP uses intdiv for integer division and substr with a start and length parameter.

Practice Makes Perfect

Once you are comfortable with the expand-around-center technique, try these related problems to build on your palindrome skills:

• Palindromic Substrings - Count the total number of palindromic substrings (same helper, different tracking)
• Longest Palindromic Subsequence - DP on subsequences rather than contiguous substrings
• Palindrome Partitioning - Minimum cuts to split a string into palindromes

This problem and thousands of others are available on Firecode, where over 50,000 users have successfully prepared for technical interviews and landed six and seven-figure jobs at top tech companies. Whether you are just starting or aiming for your next role at a FAANG company, building a strong foundation in string algorithms will serve you well.

Happy coding, and may all your substrings read the same in both directions!