SWE Prep

Share this post
Longest Palindromic Substring
sweprep.substack.com

Longest Palindromic Substring

Sameer Khoja
Jan 22, 2021
Share this post
Longest Palindromic Substring
sweprep.substack.com

👋 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.

See Approach 1

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

See Approach 2

We’re done!

Computer Rage GIFs - Get the best GIF on GIPHY

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.

Share this post
Longest Palindromic Substring
sweprep.substack.com
TopNew

No posts

Ready for more?

© 2022 Sameer Khoja
Privacy ∙ Terms ∙ Collection notice
Publish on Substack Get the app
Substack is the home for great writing