Question was to find all possible palindromic substrings of a given string.I answered O(n^2) method where I generated all the substrings and checked if they are palindrome.But they expected more optimized answer.
Print all the palindromic substrings of a given string

I think not n^2 still, as substr need on, and still n^3
//
// Created by richard on 16228.
//#include <string.h> #include <bits/stdc++.h> using namespace std; vector<string> generatePalindrome(string& str) { int len = str.size(); bool dp[len][len] ; memset(dp, sizeof dp, 1); for(int l = 2 ; l <= len; l ++ ) { for(int i = 0; i < len; i ++ ) { int j = i + l  1; if(j>=len) { continue; } dp[i][j] = dp[i+1][j1] && str[i] == str[j]; } } vector<string> ans; for(int i = 0; i < len; i ++) { for(int j = i; j < len; j ++ ) { if(dp[i][j]) { ans.push_back(str.substr(i, j  i + 1)); } } } return ans; }

This is an O(n^2) solution. And does not use extra space that dp would use. Auxillary space is needed for storing results to avoid duplicate values from result.
The approach is simple. Pick a character and move left and right from it. If these strings are palindromic then continue moving else break. Tricky part is to handle Palindromic strings of Odd and Even lengths.
/**

Find all the Palindromic substrings of a given string.

Link:

http://www.geeksforgeeks.org/findnumberdistinctpalindromicsubstrings

givenstring/

@author shivam.maharshi
*/
public class PrintAllPalindromicSubstrings {/*
 The idea is to simply pick every character and move both the sides till
 the characters are same on the end. If they are not, then you break of
 the loop because if the substring is not a palindrome than the bigger
 string will not be a plaindrome too. TimeComplexity: O(n^2). Brute force
 is O(n^3). Generation of all substring of a string is itself O(n^2),
 hence this is an optimal solution.
*/
public static Set<String> printAll(String s) {
Set<String> res = new HashSet<>();
for (int i = 0; i < s.length(); i++) {
StringBuilder sb = new StringBuilder();
int j = i, k = i + 1;
res.add(s.charAt(i) + "");
for (int it = 0; it < 2; it++) {
if (it == 1) {
j = i  1;
k = i + 1;
sb.setLength(0);
sb.append(s.charAt(i));
}
while (j >= 0 && k < s.length()) {
if (s.charAt(j) == s.charAt(k)) {
sb.insert(0, s.charAt(j));
res.add(sb.append(s.charAt(k)).toString());
j;
k++;
} else
break;
}
}
}
return res;
}
public static void main(String[] args) {
for (String s : printAll("abcbad"))
System.out.println(s);
}
}


@k' I don't think O(n) is possible since the questions asks for all substring and not the longest. I think O(n^2) is the best we can do.
Reference: http://www.geeksforgeeks.org/findnumberdistinctpalindromicsubstringsgivenstring/

@shivam.maharshi Please see below from Wikipedia page
Manacher (1975) found a linear time algorithm for listing all the palindromes that appear at the start of a given string. However, as observed e.g., by Apostolico, Breslauer & Galil (1995), the same algorithm can also be used to find all maximal palindromic substrings anywhere within the input string, again in linear time.


@shivam.maharshi my pleasure, but honestly I think it's just not fair to ask this question in 45 minutes interview and expect to answer it if you don't know the algorithm, that's my opinion anyways

@k' I agree. When they ask questions on the algorithms that people publish in paper IMO it's mostly to check your knowledge rather than analytical skills. Maybe it's important for them may be not. But I think that @shashank23 used native library substring function which made the algo O(n^3) instead. Hence I think they were expecting O(n^2).

@shivam.maharshi Your solution is O(n^3). You use StringBuilder to avoid calling substring(), but insert() method is O(n).

@k' Just a simple addition, I think there are possibly \Omega(n^2) palindromes in a string. Therefore Manacher's algorithm can list all the palindromes in an implicit way as if you are required to print out all palindromes with each starting indices and ending indices, the task is already \Omega(n^2). The thing is that Manacher's algorithm can find the longest palindromes centered at any character, therefore it implicitly list all palindromes.

Let's do a simple centerandexpand method. This isn't the most ideal method (Manacher's is involved) but it is a typical method that interviewers are looking for.
def solve(S): ans = set() N = len(S) for center in xrange(2*N  1): left = center / 2 right = left + center % 2 while 0 <= left and right < len(S) and S[left] == S[right]: ans.add(S[left: right+1]) left = 1 right += 1 return ans

Here is a method using Manacher's algorithm.
def manachers(S): SS = '#' + '#'.join(S) + '#' Z = [0] * len(SS) center = right = 0 for i in xrange(1, len(SS)): if i < right: Z[i] = min(right  i, Z[2 * center  i]) while (min(len(SS)  i  1, i) > Z[i] and SS[i + Z[i] + 1] == SS[i  Z[i]  1]): Z[i] += 1 if i + Z[i] > right: center, right = i, i + Z[i] return Z def solve(S): M = manachers(S)[1: 1] ans = set() for center, expand in enumerate(M): for e in xrange(expand + 1): ans.add(S[(center  e)/2 : (center + e)/2]) return ans

public static void listPalindrome(string s) { for (int i = 0; i < s.Length; i++) { //assuming minimum length of string is 2 for (int j = 2; j < s.Length; j++) { if (i + j < s.Length) { char[] x = s.Substring(i, j + 1).ToCharArray(); string o = new string(x); Array.Reverse(x); string n = new string(x); if (o.Equals(n)) { Console.WriteLine(o); } } } } }

void countpalin(string str,int lo,int hi)
{
int n=str.length(),cnt=0;
while(lo>=0 && hi<n)
{
if(str[lo]!=str[hi])
break;
myset.insert(str.substr(lo,hilo+1));
lo;hi++;
}
}
int palindromeCount(string str) {
int n=str.length();
int cnt=0;
for(int i=0;i<n;i++)
{
myset.insert(str.substr(i,1));
countpalin(str,i1,i+1);
if(i+1<n && str[i]==str[i+1])
{
myset.insert(str.substr(i,2));
countpalin(str,i1,i+1);
}} return myset.size();
}
Can someone help me understand that why this method fails ? Or even testcases where it fails :)