Longest Palindromic Substring

👋 Hello! I’m gathering feedback on SWE Prep. If you like to provide suggestions or feedback, let us know on this survey here!

Question: Given a string, find the longest palindromic substring within the string.

Solution

Approach 1: Brute Force

We could simply examine every substring and check if it is palindromic. This would have a time complexity of O(n^3), which is not a great start but technically a solution that works.

Approach 2: Dynamic Programming

Let s be the input string, i and j are two indexes of the string.

We can define a 2-dimensional array, “table”, in which table[ i ][ j ] denotes whether the substring from index i to index j is a palindrome (boolean true or false).

Our table will take on the following starting and changing conditions.

• table[i][i] == 1;

• If table[i][i + 1] == 1, then s.charAt(i) == s.charAt(i + 1)

• If table[i+1][j-1] == 1 && s.charAt(i) == s.charAt(j), then table[i][j] == 1

We’re done!

---

Interested in breaking into Computer Science? Eager to expand your knowledge base and learn new things? Enjoy problem solving? If so, this newsletter is for you. Subscribe to get fully explained interview prompts commonly given in engineering interviews, from Arrays to Dynamic Programming. Questions come out weekly and are also categorized by subject and difficulty.

Subscribe to get full access to the newsletter. Never miss an update.