Tag Archives: substring

Longest sub-string with no duplicate chars

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for “abcabcbb” is “abc”, which the length is 3. For “bbbbb” the longest substring is “b”, with the length of 1. The trivial solution would be to do double for loop and from each […]

Longest palindromic substring in O(n^2) time

Given a string, find the longest substring that is also a palondrom. One simple solution is to find reverse of S and then find the longest common substring between S and reverse(s). This is also be the longest palindromic substring. That is, LongestPalindromicSubStr(S) = LCS(S, reverse(S)). LCS can be solved by DP in O(n^2) time […]