Epic Systems Interview Question Software Engineer / Developers
Country: United States
#include <stdio.h>
#include<string.h>
void print(char a[],int low,int high)
{
int i;
for(i=low;i<=high;i++)
printf("%c",a[i]);
printf("\n");
return;
}
void palin(char a[],int n)
{
int i,low,high;
for(i=1;i<n;i++)
{
low=i-1;
high=i;
while(low>=0 && high<n && a[low]==a[high])
{
if(high-low+1>=3)
{
print(a,low,high);
}
low--;
high++;
}
low=i-1;
high=i+1;
while(low>=0 && high<n && a[low]==a[high])
{
if(high-low+1>=3)
{
print(a,low,high);
}
low--;
high++;
}
}
}
int main(void) {
// your code goes here
char a[16]="cabbaabbacasdasdsdsdsdassadsadasdasadsadasda";
palin(a,strlen(a));
return 0;
}
Time complexity: O(n^2)
Space complexity: O(1)
public static void main(String[] args)
{
String str = "cabbaabbacasdasdsdsdsdassadsadasdasadsadasda";
System.out.println("String: " + str);
findPalindromes(str, 1, 3);
}
public static void findPalindromes(String str, double mid, int minSize)
{
if(mid < str.length())
{
check(str, (int)Math.floor(mid), (int)Math.ceil(mid), minSize);
mid = mid + 0.5;
findPalindromes(str, mid, minSize);
}
}
public static void check(String str, int start, int end, int minSize)
{
if(start >= 0 && end < str.length() && str.charAt(start) == str.charAt(end))
{
if(end - start + 1 >= minSize)
{
System.out.println(str.substring(start, end + 1));
}
check(str, start - 1, end + 1, minSize);
}
}
Awesome Code, But one miss...
It could not find even length palindrome.
Example:
findPalindrome("ababa",0,3);
Output
aba
bab
ababa
aba
String baba is missing in the output!
Baba is not a palindrome!
Looks like a neat piece of code..
Below debug lines may help some one understand better..
package Epic;
public class palindrome {
//Print all palindromes of size greater than equal to 3 of a given string (DP)
public static void main(String[] args)
{
String str = "ababa";
//String str = "cabbaabbacasdasdsdsdsdassadsadasdasadsadasda";
System.out.println("String: " + str);
findPalindromes(str, 1, 3);
}
public static void findPalindromes(String str, double mid, int minSize)
{
System.out.println("Mid value is: "+mid);
if(mid < str.length())
{
check(str, (int)Math.floor(mid), (int)Math.ceil(mid), minSize);
mid = mid + 0.5;
findPalindromes(str, mid, minSize);
}
else
{
System.out.println("Mid is greater than string length");
}
}
public static void check(String str, int start, int end, int minSize)
{
if(start >= 0 && end < str.length() && str.charAt(start) == str.charAt(end))
{
System.out.println("=======================================================");
System.out.println("Start value is: "+start);
System.out.println("End value is: "+end);
System.out.println("Char at 'start' is : "+str.charAt(start)+ " Char at 'end' is : "+str.charAt(end));
if(end - start + 1 >= minSize)
{
System.out.println(str.substring(start, end + 1));
}
System.out.println("The contained string is a palindrome, wrap one char at beginning and end");
check(str, start - 1, end + 1, minSize);
}
else if (start <= 0)
{
System.out.println("Start less than 0");
}
else if(end >=str.length() )
{
System.out.println("End greater than string length");
}
else
{
System.out.println("Start : "+ str.charAt(start) + " and End: " +str.charAt(end) +" not same");
}
}
}
If you ever heard of Manacher's algorithm, then you will know that there is a O(N), O(N) solution out there.
Just to make my life easier, here is my O(N^2), O(N) bottom-up DP code. No recursion. Idea is simple, if I want to check whether S[i->j] is a palindrome or not, i check: S.charAt[i] == S.charAt[j] and substring from i to j is less than 3 char long, or S[i+1, j-1] is a palindrome.
Playable code at:
ideone.com/c2BXDf
void checkPalindrome(string s) {
if (s.size() < 3) return;
vector<bool> memo(s.size(), 0);
for (int i = s.size() - 1; i >= 0; --i) {
for (int j = s.size() - 1; j >= i; --j) {
if (s[i] == s[j] && (j <= i + 1 || memo[j - 1])) {
memo[j] = 1;
if (j - i + 1 >= 3)
cout << s.substr(i, j - i + 1) << endl;
}
else memo[j] = 0;
}
}
}
public class palindromeStrings {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
String temp="abbppqqwoooopxyz";
int[] table=new int[26];
String alpha="abcdefghijklmnopqrstuvwxyz";
for(int i=0;i<temp.length();i++)
{
table[(temp.charAt(i)-'a')]+=1;
}
pal("",table,alpha,0);
}
public static void pal(String str,int[] table,String alpha, int n)
{
if(n>=3)
{
System.out.println(str);
return;
}
else
{
if(str.length()==0)
{
//System.out.println("yo");
for(int i=0;i<table.length;i++)
{
System.out.println("yo");
if(table[i]==1)
{
table[i]-=1;
pal(str+alpha.charAt(i),table,alpha,n+1);
}
else if(table[i]>=2)
{
table[i]=table[i]-2;
pal(alpha.charAt(i)+str+alpha.charAt(i),table,alpha,n+2);
table[i]=table[i]+2;
table[i]=table[i]-1;
pal(str+alpha.charAt(i),table,alpha,n+1);
}
else
continue;
}
}
for(int i=0;i<table.length;i++)
{
if(table[i]>=2)
{
table[i]=table[i]-2;
pal(alpha.charAt(i)+str+alpha.charAt(i),table,alpha,n+2);
}
}
}
}
}
ya...
1. store the count of each character in array
2. for each character in an array,
iterate through array & append to output
if str.length==0
then get one char & decremnt count for that particular char
else
if count for that char is >=2
then (char+str+char) thhis will be the string for palindrome.
if length>3 print it.
My understanding is that we need to find palindromes in the existing string. If I store the frequency of characters then I have lost the original order of chars. Your code will work for the problem where we have to print all palindromes that can be formed using the characters in the string. This is a slightly different problem.
public class palindromeStrings {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
String temp="abbppqqwoooopxyz";
int[] table=new int[26];
String alpha="abcdefghijklmnopqrstuvwxyz";
for(int i=0;i<temp.length();i++)
{
table[(temp.charAt(i)-'a')]+=1;
}
pal("",table,alpha,0);
}
public static void pal(String str,int[] table,String alpha, int n)
{
if(str.length()==0)
{
//System.out.println("yo");
for(int i=0;i<table.length;i++)
{
//System.out.println("yo");
if(table[i]==1)
{
table[i]-=1;
pal(str+alpha.charAt(i),table,alpha,n+1);
}
else if(table[i]>=2)
{
table[i]=table[i]-2;
pal(alpha.charAt(i)+str+alpha.charAt(i),table,alpha,n+2);
table[i]=table[i]+2;
table[i]=table[i]-1;
pal(str+alpha.charAt(i),table,alpha,n+1);
}
else
continue;
}
}
for(int i=0;i<table.length;i++)
{
if(table[i]>=2)
{
table[i]=table[i]-2;
String temp=""+alpha.charAt(i)+str+alpha.charAt(i);
if(n+2>=3)
System.out.println(temp);
pal(alpha.charAt(i)+str+alpha.charAt(i),table,alpha,n+2);
}
}
}
}
I propose this solution:
1) Check for odd palindromes starting from the second character and advancing left and right. There is no need for caching as we move one step at the time, and we print it out at every step if the palindrome condition holds.
2) Check even length palindroms starting from the second characted again but with left=i-1 and right = i.
public void evenPalindromes(char[] array){
for(int i=1;i<array.length;i++){
//check left and right
int left = i-1;
int right = i;
checkExpansion(array,left,right);
}
}
public void oddPalindromes(char[] array){
for(int i=1;i<array.length-1;i++){
//check left and right
int left = i-1;
int right = i+1;
checkExpansion(array,left,right);
}
}
public void checkExpansion(char[] array, int left, int right){
while(array[left]==array[right]){
for(int j=left;j<=right;j++){
System.out.print(array[j]);
}
left--;
right++;
System.out.println();
if(left < 0 || right >= array.length) return;
}
}
public class PalindromeInString {
public static void main(String[] args){
String orginal = "bccbaabcedtdecb";
FindPld(orginal);
}
static void FindPld(String s){
char[] cha = s.toCharArray();
for(int i= 2; i <s.length()-3; i++){
if(cha[i] == cha[i+1]){
int size = 1;
if(i<s.length()/2+1){
for(int j= 1; j<i+1; j++){
if(cha[i-j] == cha[i+1+j]){
size++;
}
}
}else{
for(int j= 1; j<s.length()-i-1; j++){
if(cha[i-j] == cha[i+1+j]){
size++;
}
}
}
if(size >2 && size<s.length()){
System.out.println(s.substring(i-size+1, i+size+1));
}
}
}
}
}
Below is the code based on logic suggested by kr.neerav
#include <iostream>
#include <string>
using namespace std;
int main()
{
string s;
cin>>s;
int *a=new int[s.length()]; //=new int[s.length()];
memset ( a,0,sizeof ( int ) * ( s.length() ) ) ;
int k;
//a[0]=0;
for ( int i=1; i<s.length(); i++ )
{
if ( a[i-1]==0 )
{
if ( s[i-1]==s[i] )
{
a[i]+=2;
}
if ( ( i-2 ) >=0 )
{
if ( s[i-2]==s[i] )
{
a[i]+=3;
}
}
}
else
{
if ( ( i-1-a[i-1] ) >=0 )
{
if ( s[i-1-a[i-1]]==s[i] )
{
a[i]+=a[i-1]+2;
}
}
else {
a[i]+=a[i-1]+1;
}
}
}
for ( int i=0; i<s.length(); i++ ) {
if ( a[i]>=3 )
{
for ( int j=i-a[i]+1; j<=i; j++ ) {
cout<<s[j];
}
cout<<",";
}
}
getchar();
}
import java.util.ArrayList;
public class PalindromeFinder
{
public static ArrayList<String> getPalindromes(String s)
{
ArrayList<String> initialPalindromes = new ArrayList<String>();
for (int i = 0; i < s.length(); i++)
{
String currentPalindrome = s.charAt(i) + "";
int j = 1;
boolean palindromeEnded = false;
while (i - j >= 0 && i + j < s.length() && !palindromeEnded)
{
if (s.charAt(i - j) == s.charAt(i + j))
currentPalindrome = s.charAt(i - j) + currentPalindrome
+ s.charAt(i + j);
else
palindromeEnded = true;
j++;
}
if (currentPalindrome.length() >= 3)
{
initialPalindromes.add(currentPalindrome);
}
}
ArrayList<String> finalPalindromes = new ArrayList<String>();
for (String palindrome : initialPalindromes)
{
int palLingth = palindrome.length();
int maxOffset = (palindrome.length() / 2) - 1;
for (int i = 0; i <= maxOffset; i++)
finalPalindromes
.add(palindrome.substring(0 + i, palLingth - i));
}
return finalPalindromes;
}
public static void main(String args[])
{
String s = "abcdefedcba1234543454321";
ArrayList<String> palindromes = getPalindromes(s);
for (String palindrome : palindromes)
System.out.println(palindrome);
}
}
import java.util.ArrayList;
public class PrintAllPalindrome {
public static void main(String [] st){
ArrayList <String > al=allPalindrome("123454321");
for(int i=0;i<al.size();i++){
System.out.println(al.get(i));
}
}
public static ArrayList<String> allPalindrome(String st){
ArrayList <String> al=new ArrayList <String>();
for(int window=3;window<st.length();window++){
for(int index=0;index<st.length()-window;index++){
String string = isPalindrome((String)st.substring(index, index+window+1));
if(!string.equals(""))
al.add(string);
}
}
return al;
}
public static String isPalindrome(String string){
int index=0,length=string.length();
while(string.charAt(index)==string.charAt(length-index-1) ){
if( index>(length-index-1)) return string;
index++;
}
//System.out.println(string);
return "" ;
}
}
public class FindPalindrome {
public static boolean isPalindrome(String s){
if (s.length() < 3) {
return false;
}
int start = 0;
int end = s.length() - 1;
while (start < end ) {
if (s.charAt(start) != s.charAt(end)){
return false;
}
start++;
end--;
}
return true;
}
public static void main(String[] args) {
StringBuilder sb = new StringBuilder();
String s = "abccbadddabccba";
helper(s, sb, 0);
}
public static void helper(String s, StringBuilder sb, int pos){
if (isPalindrome(sb.toString())){
System.out.println(sb.toString());
}
for( int i = pos; i < s.length(); i++) {
sb.append(s.charAt(i));
helper(s, sb, i + 1);
sb.deleteCharAt(sb.length() - 1);
}
}
}
public class checkPalindrome {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner s = new Scanner(System.in);
System.out.println("Enter a string ");
String str= s.next();
int len = str.length();
for(int i=0;i<(len-2);i++)
{
int y=i+3;
while(y<=len)
{
if(checkPalindrome(str.substring(i, y)))
System.out.println(str.substring(i, y));
y++;
}
}
}
private static boolean checkPalindrome(String substring) {
// TODO Auto-generated method stub
int j = substring.length();
j--;
int i=0;
boolean b= true;
while(i<j)
{
if(substring.charAt(i)!=substring.charAt(j))
{
b=false;
break;
}
i++;
j--;
}
return b;
}
}
Can be done using recursion and one for loop
public static void printPalindrome(String str)
{ if(str.length()<1)
System.exit(0);
for(int j =3;j<=str.length();j++)
{
String temp = str.substring(0,j);
String reverse = new StringBuffer(temp).reverse().toString();
if(temp.equals(reverse)){
System.out.println(temp);
}
}//j-for
printPalindrome(str.substring(1));
}//printPalindrome
#include <string>
#include <iostream>
using namespace std;
bool isPalindrome(string str)
{
if ((str.length() == 0) || str.length() == 1) return true;
if (toupper(str[0]) != toupper(str[str.length() - 1])) return false;
str = str.substr(1, str.length() - 2);
return isPalindrome(str);
}
void printPalin(string str) {
if (str.length() < 3) return;
for (int i = 0; i < str.length() - 2; ++i) {
for (int j = i + 2; j < str.length(); ++j) {
if (isPalindrome(str.substr(i, j - i + 1))) {
cout << str.substr(i, j - i + 1) << endl;
}
}
}
}
void main() {
string s = "abaddddsdsd";
printPalin(s);
cin.get();
}
public class PalindromeThreePlus{
public static void main(String args[]){
String myString = "cabbaabbacasdasdsdsdsdassadsadasdasadsadasda";
for(int i = 0; i<myString.length();i++){
for(int j = i+3; j<=myString.length();j++){
String tempString = myString.substring(i,j);
if(tempString.length()>=3 && checkPalindrome(tempString)){
System.out.println(tempString);
}
}
}
}
public static boolean checkPalindrome(String tempString){
int i = 0;
int j = tempString.length()-1;
while(i<j){
if(tempString.charAt(i) != tempString.charAt(j)){
return false;
}
i++;
j--;
}
return true;
}
}
#include <iostream>
#include <math.h>
#include <string>
using namespace std;
void LongestCommonSubStr(char* s1, char* s2, int m, int n)
{
int **L = new int*[m+1];
for(int i = 0; i<m+1; i++)
L[i] = new int[n+1];
for(int i = 0; i<=m ; i++)
{
for(int j = 0; j <= n; j++)
{
if(i == 0 || j == 0)
L[i][j] = 0;
if(s1[i-1] == s2[j-1])
L[i][j] = L[i-1][j-1] + 1;
else
L[i][j] = 0;
}
}
for(int i = 0; i <= m; i++)
{
for(int j = 0; j<= n; j++)
{
if(L[i][j] >= 3)
{
if((i < m && j < n && L[i+1][j+1] == 0) || (i == m || j == n))
{
//Found a common substring of length >= 3
//actual indexes start from i-L, j-L
string substring;
for(int start = i-L[i][j]; start < i; start++)
substring.push_back(s1[start]);
cout<<substring<<"\n";
}
}
}
}
}
int main()
{
char s1[] = "abaxynitincaac";
char s2[] = "caacnitinyxaba";
LongestCommonSubStr(s1,s2, 14, 14);
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace matrix
{
class Program
{
static void Main(string[] args)
{
string chk_palin = "asdsatftfdsdfyuyfds";
for (int i = 3; i < chk_palin.Length; i++)
{
int Length = i-1;
int start = 0;
for (int j = 0; j < chk_palin.Length-i; j++)
{
start = j;
int end = start + Length;
bool pali = true;
while (start < end && start>=0 && end<chk_palin.Length)
{
if (chk_palin[start] == chk_palin[end])
{
start++;
end--;
}
else
{
pali = false;
break;
}
}
if (pali)
Print(chk_palin.Substring(j, Length+1));
}
}
}
private static void Print(string p)
{
// for (int s = 0; s < p.Length; s++)
Console.Write(p);
Console.WriteLine();
}
}
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace matrix
{
class Program
{
static void Main(string[] args)
{
string chk_palin = "asdsatftfdsdfyuyfds";
for (int i = 3; i < chk_palin.Length; i++)
{
int Length = i-1;
int start = 0;
for (int j = 0; j < chk_palin.Length-i; j++)
{
start = j;
int end = start + Length;
bool pali = true;
while (start < end && start>=0 && end<chk_palin.Length)
{
if (chk_palin[start] == chk_palin[end])
{
start++;
end--;
}
else
{
pali = false;
break;
}
}
if (pali)
Print(chk_palin.Substring(j, Length+1));
}
}
}
private static void Print(string p)
{
// for (int s = 0; s < p.Length; s++)
Console.Write(p);
Console.WriteLine();
}
}
}
Logic: consider the case “ababa”. If we already knew that “bab” is a palindrome, it is obvious that “ababa” must be a palindrome since the two left and right end letters are the same.
Let's dp[i][j] be the palindrome starting from i to j in the sequence "ababa" where i and j is the position of the character in the aforementioned string.
As already mentioned we have to find out if the given string is palindrome or not? We first find out if the inner string is palindrome and then use that insight as below:
"anina" --here we first find out "nin" is palindrome or not and then compare 0 and 4 character to find out if this whole string is palindrome or not?
"aaninaa" now as we already found out "anina" is palindrome we use that insight to find out if the aforementioned is palindrome or not?
We do this for all [i and j] which results in n^2 solution.
void print_string_from_i_to_j(char *a, int k, int j)
{
int last_char = j-k+1, i;
char *dp = malloc(last_char);
memset(dp, 0, last_char);
for(i=0;i<last_char;i++) {
dp[i] = a[k++];
}
dp[last_char] = '\0';
printf("%s\n", dp);
}
void print_all_palindrome(char *a, int size)
{
int i, k;
int **dp = malloc(sizeof(int *)*(size));
for (i=0;i<size;i++) {
dp[i] = malloc(sizeof(int)*size);
}
/* all single character are considered palindrome */
for (i=0;i<size;i++)
dp[i][i] = 1;
/* compare the consecutive elements */
for (i=0;i<size-1;i++)
if (a[i] == a[i+1])
dp[i][i+1] = 1;
for (k=3;k<size;k++) {
for (i=0;i<size-k+1;i++) {
int j = i+k-1;
printf("i %d j %d\n", i, j);
if ((a[i] == a[j]) && dp[i+1][j-1]) {
dp[i][j] = 1;
if(dp[i][j])
print_string_from_i_to_j(a, i, j);
} else if(dp[i][j])
print_string_from_i_to_j(a, i, j);
}
printf("\n\n");
}
}
int main()
{
char a[] = {"sbninbsh"};
print_all_palindrome(a, strlen(a));
return 0;
}
public class palindromes {
public static String reverse(String s1){
String s2= "";
for(int i = s1.length()-1; i>=0 ;i--)
{
s2 = s2 + s1.substring(i,i+1);
}
//System.out.println("String is:" +s1.length()+ " and reverse is:" +s2.length());
return s2;
}
public static void check_palindromes(String s)
{
for(int k= 3; k <=s.length();k++)
{
for(int i = 0; i<= s.length()-k; i++)
{
String str = s.substring(i,i+k);
if(str.equals(reverse(str)))
{
System.out.println(str);
}
}
}
}
public static void main(String argv[])
{
check_palindromes("ababa");
}
}
package EPIC;
public class Palindrome {
public static void printPalindrome(String S) {
boolean dp[][] = new boolean[S.length()][S.length()];
for (int i = 0; i <= dp.length - 1; i++) {
dp[i][i] = true;
}
for (int i = 0; i <= dp.length - 2; i++) {
if (S.charAt(i) == S.charAt(i + 1)) {
dp[i][i + 1] = true;
}
}
for (int diag = 1; diag <= dp.length - 1; diag++) {
for (int i = 0; i <= dp.length - diag - 1; i++) {
if ( S.charAt(i + diag) == S.charAt(i) && dp[i + diag - 1][i + 1] == true ) {
dp[i + diag][i] = true;
if (diag + 1 >= 3) {
System.out.println(S.substring(i, i + diag + 1));
}
}
}
}
pringDP(dp);
}
public static void pringDP(boolean dp[][]) {
for (int i = 0; i < dp.length; i++) {
for (int j = 0; j < dp.length; j++) {
if (dp[i][j]) {
System.out.print(1 + " ");
} else {
System.out.print(0 + " ");
}
}
System.out.println();
}
}
public static void main(String[] args) {
// printPalindrome("abcbbde");
printPalindrome("cabbaabbacasdasdsdsdsdassadsadasdasadsadasda");
}
}
package Epic;
public class palindrome {
//Print all palindromes of size greater than equal to 3 of a given string (DP)
public static void main(String[] args)
{
String str = "ababa";
//String str = "cabbaabbacasdasdsdsdsdassadsadasdasadsadasda";
System.out.println("String: " + str);
findPalindromes(str, 1, 3);
}
public static void findPalindromes(String str, double mid, int minSize)
{
System.out.println("Mid value is: "+mid);
if(mid < str.length())
{
check(str, (int)Math.floor(mid), (int)Math.ceil(mid), minSize);
mid = mid + 0.5;
findPalindromes(str, mid, minSize);
}
else
{
System.out.println("Mid is greater than string length");
}
}
public static void check(String str, int start, int end, int minSize)
{
if(start >= 0 && end < str.length() && str.charAt(start) == str.charAt(end))
{
System.out.println("=======================================================");
System.out.println("Start value is: "+start);
System.out.println("End value is: "+end);
System.out.println("Char at 'start' is : "+str.charAt(start)+ " Char at 'end' is : "+str.charAt(end));
if(end - start + 1 >= minSize)
{
System.out.println(str.substring(start, end + 1));
}
System.out.println("The contained string is a palindrome, wrap one char at beginning and end");
check(str, start - 1, end + 1, minSize);
}
else if (start <= 0)
{
System.out.println("Start less than 0");
}
else if(end >=str.length() )
{
System.out.println("End greater than string length");
}
else
{
System.out.println("Start : "+ str.charAt(start) + " and End: " +str.charAt(end) +" not same");
}
}
}
package Epic;
import java.util.Scanner;
public class containsPalindrome_len3 {
public static void main(String a[]) {
System.out.println("Enter to string name to check for palindrome");
Scanner sc = new Scanner(System.in);
String input_str = sc.next();
if (input_str.length() >= 3) {
for (int k = 3; k < input_str.length() - 3; k++) {
for (int i = 0; i < input_str.length() - k; i++) {
boolean isPalin = isPalindrome(input_str
.substring(i, i + k));
if (isPalin == true)
System.out.println("String length:" + k + "::"
+ input_str.substring(i, i + k));
}
}
}
}
private static boolean isPalindrome(String substring) {
for (int i = 0, j = substring.length() - 1; i < j;) {
if (substring.charAt(i) != substring.charAt(j)) {
if (!(substring.charAt(i) >= 65 && substring.charAt(i) <= 90 || substring
.charAt(i) >= 97 && substring.charAt(i) <= 122))
i++;
else if (!(substring.charAt(j) >= 65
&& substring.charAt(j) <= 90 || substring.charAt(j) >= 97
&& substring.charAt(j) <= 122))
j--;
else if (substring.charAt(i) - 32 == substring.charAt(j)
|| substring.charAt(i) == substring.charAt(j) - 32) {
i++;
j--;
} else
return false;
}
else {
i++;
j--;
}
}
return true;
}
}
package Epic;
import java.util.Scanner;
public class containsPalindrome_len3 {
public static void main(String a[]) {
System.out.println("Enter to string name to check for palindrome");
Scanner sc = new Scanner(System.in);
String input_str = sc.next();
if (input_str.length() >= 3) {
for (int k = 3; k < input_str.length() - 3; k++) {
for (int i = 0; i < input_str.length() - k; i++) {
boolean isPalin = isPalindrome(input_str
.substring(i, i + k));
if (isPalin == true)
System.out.println("String length:" + k + "::"
+ input_str.substring(i, i + k));
}
}
}
}
private static boolean isPalindrome(String substring) {
for (int i = 0, j = substring.length() - 1; i < j;) {
if (substring.charAt(i) != substring.charAt(j)) {
if (!(substring.charAt(i) >= 65 && substring.charAt(i) <= 90 || substring
.charAt(i) >= 97 && substring.charAt(i) <= 122))
i++;
else if (!(substring.charAt(j) >= 65
&& substring.charAt(j) <= 90 || substring.charAt(j) >= 97
&& substring.charAt(j) <= 122))
j--;
else if (substring.charAt(i) - 32 == substring.charAt(j)
|| substring.charAt(i) == substring.charAt(j) - 32) {
i++;
j--;
} else
return false;
}
else {
i++;
j--;
}
}
return true;
}
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace Factorial
{
class Program
{
static void Main(string[] args)
{
char[] str;
string _str = "";
Console.WriteLine("Please enter a string to check Paladin");
str = Console.ReadLine().ToCharArray();
{
if (str.Length == 3)
{
if (ifPaladine(str, 0, str.Length - 1))
{
Console.WriteLine("It Is Paladine");
Console.ReadKey();
}
else
{
Console.WriteLine("Not a paladine");
Console.ReadKey();
}
}
else if (str.Length < 3)
{
Console.WriteLine("Invalid input");
return;
}
else if (str.Length > 3)
{
string result = "";
for (int x = 0; x < str.Length - 3; x++)
{
for (int y = x + 3; y <= str.Length; y++)
{
for (int z = x; z < y; z++)
{
_str = _str + str[z];
}
if (ifPaladine(_str.ToCharArray(), 0, _str.Length - 1))
{
result = result + " " + _str;
_str = "";
}
else
_str = "";
}
}
if (result.Equals(String.Empty))
Console.WriteLine("No Paladin found");
else
Console.WriteLine(result.ToString());
Console.ReadKey();
}
}
}
public static void printString(string[] str)
{
for (int i = 0; i < str.Length; i++)
{
Console.WriteLine(String.IsNullOrEmpty(str[i].ToString()));
}
}
public static Boolean ifPaladine(char[] ar, int start, int end)
{
string reverse = "";
for (int i = ar.Length-1; i >=0; i--)
{
reverse = reverse + ar[i];
}
string c = new string(ar);
if (c.ToLower() == reverse.ToString().ToLower())
return true;
else
return false;
}
}
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace Factorial
{
class Program
{
static void Main(string[] args)
{
char[] str;
string _str = "";
Console.WriteLine("Please enter a string to check Paladin");
str = Console.ReadLine().ToCharArray();
{
if (str.Length == 3)
{
if (ifPaladine(str, 0, str.Length - 1))
{
Console.WriteLine("It Is Paladine");
Console.ReadKey();
}
else
{
Console.WriteLine("Not a paladine");
Console.ReadKey();
}
}
else if (str.Length < 3)
{
Console.WriteLine("Invalid input");
return;
}
else if (str.Length > 3)
{
string result = "";
for (int x = 0; x < str.Length - 3; x++)
{
for (int y = x + 3; y <= str.Length; y++)
{
for (int z = x; z < y; z++)
{
_str = _str + str[z];
}
if (ifPaladine(_str.ToCharArray(), 0, _str.Length - 1))
{
result = result + " " + _str;
_str = "";
}
else
_str = "";
}
}
if (result.Equals(String.Empty))
Console.WriteLine("No Paladin found");
else
Console.WriteLine(result.ToString());
Console.ReadKey();
}
}
}
public static void printString(string[] str)
{
for (int i = 0; i < str.Length; i++)
{
Console.WriteLine(String.IsNullOrEmpty(str[i].ToString()));
}
}
public static Boolean ifPaladine(char[] ar, int start, int end)
{
string reverse = "";
for (int i = ar.Length-1; i >=0; i--)
{
reverse = reverse + ar[i];
}
string c = new string(ar);
if (c.ToLower() == reverse.ToString().ToLower())
return true;
else
return false;
}
}
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace Factorial
{
class Program
{
static void Main(string[] args)
{
char[] str;
string _str = "";
Console.WriteLine("Please enter a string to check Paladin");
str = Console.ReadLine().ToCharArray();
{
if (str.Length == 3)
{
if (ifPaladine(str, 0, str.Length - 1))
{
Console.WriteLine("It Is Paladine");
Console.ReadKey();
}
else
{
Console.WriteLine("Not a paladine");
Console.ReadKey();
}
}
else if (str.Length < 3)
{
Console.WriteLine("Invalid input");
return;
}
else if (str.Length > 3)
{
string result = "";
for (int x = 0; x < str.Length - 3; x++)
{
for (int y = x + 3; y <= str.Length; y++)
{
for (int z = x; z < y; z++)
{
_str = _str + str[z];
}
if (ifPaladine(_str.ToCharArray(), 0, _str.Length - 1))
{
result = result + " " + _str;
_str = "";
}
else
_str = "";
}
}
if (result.Equals(String.Empty))
Console.WriteLine("No Paladin found");
else
Console.WriteLine(result.ToString());
Console.ReadKey();
}
}
}
public static void printString(string[] str)
{
for (int i = 0; i < str.Length; i++)
{
Console.WriteLine(String.IsNullOrEmpty(str[i].ToString()));
}
}
public static Boolean ifPaladine(char[] ar, int start, int end)
{
string reverse = "";
for (int i = ar.Length-1; i >=0; i--)
{
reverse = reverse + ar[i];
}
string c = new string(ar);
if (c.ToLower() == reverse.ToString().ToLower())
return true;
else
return false;
}
}
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace Factorial
{
class Program
{
static void Main(string[] args)
{
char[] str;
string _str = "";
Console.WriteLine("Please enter a string to check Paladin");
str = Console.ReadLine().ToCharArray();
{
if (str.Length == 3)
{
if (ifPaladine(str, 0, str.Length - 1))
{
Console.WriteLine("It Is Paladine");
Console.ReadKey();
}
else
{
Console.WriteLine("Not a paladine");
Console.ReadKey();
}
}
else if (str.Length < 3)
{
Console.WriteLine("Invalid input");
return;
}
else if (str.Length > 3)
{
string result = "";
for (int x = 0; x < str.Length - 3; x++)
{
for (int y = x + 3; y <= str.Length; y++)
{
for (int z = x; z < y; z++)
{
_str = _str + str[z];
}
if (ifPaladine(_str.ToCharArray(), 0, _str.Length - 1))
{
result = result + " " + _str;
_str = "";
}
else
_str = "";
}
}
if (result.Equals(String.Empty))
Console.WriteLine("No Paladin found");
else
Console.WriteLine(result.ToString());
Console.ReadKey();
}
}
}
public static void printString(string[] str)
{
for (int i = 0; i < str.Length; i++)
{
Console.WriteLine(String.IsNullOrEmpty(str[i].ToString()));
}
}
public static Boolean ifPaladine(char[] ar, int start, int end)
{
string reverse = "";
for (int i = ar.Length-1; i >=0; i--)
{
reverse = reverse + ar[i];
}
string c = new string(ar);
if (c.ToLower() == reverse.ToString().ToLower())
return true;
else
return false;
}
}
}
class Program
{
static void Main(string[] args)
{
char[] str;
string _str = "";
Console.WriteLine("Please enter a string to check Paladin");
str = Console.ReadLine().ToCharArray();
{
if (str.Length == 3)
{
if (ifPaladine(str, 0, str.Length - 1))
{
Console.WriteLine("It Is Paladine");
Console.ReadKey();
}
else
{
Console.WriteLine("Not a paladine");
Console.ReadKey();
}
}
else if (str.Length < 3)
{
Console.WriteLine("Invalid input");
return;
}
else if (str.Length > 3)
{
string result = "";
for (int x = 0; x < str.Length - 3; x++)
{
for (int y = x + 3; y <= str.Length; y++)
{
for (int z = x; z < y; z++)
{
_str = _str + str[z];
}
if (ifPaladine(_str.ToCharArray(), 0, _str.Length - 1))
{
result = result + " " + _str;
_str = "";
}
else
_str = "";
}
}
if (result.Equals(String.Empty))
Console.WriteLine("No Paladin found");
else
Console.WriteLine(result.ToString());
Console.ReadKey();
}
}
}
public static void printString(string[] str)
{
for (int i = 0; i < str.Length; i++)
{
Console.WriteLine(String.IsNullOrEmpty(str[i].ToString()));
}
}
public static Boolean ifPaladine(char[] ar, int start, int end)
{
string reverse = "";
for (int i = ar.Length-1; i >=0; i--)
{
reverse = reverse + ar[i];
}
string c = new string(ar);
if (c.ToLower() == reverse.ToString().ToLower())
return true;
else
return false;
}
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace Factorial
{
class Program
{
static void Main(string[] args)
{
char[] str;
string _str = "";
Console.WriteLine("Please enter a string to check Paladin");
str = Console.ReadLine().ToCharArray();
{
if (str.Length == 3)
{
if (ifPaladine(str, 0, str.Length - 1))
{
Console.WriteLine("It Is Paladine");
Console.ReadKey();
}
else
{
Console.WriteLine("Not a paladine");
Console.ReadKey();
}
}
else if (str.Length < 3)
{
Console.WriteLine("Invalid input");
return;
}
else if (str.Length > 3)
{
string result = "";
for (int x = 0; x < str.Length - 3; x++)
{
for (int y = x + 3; y <= str.Length; y++)
{
for (int z = x; z < y; z++)
{
_str = _str + str[z];
}
if (ifPaladine(_str.ToCharArray(), 0, _str.Length - 1))
{
result = result + " " + _str;
_str = "";
}
else
_str = "";
}
}
if (result.Equals(String.Empty))
Console.WriteLine("No Paladin found");
else
Console.WriteLine(result.ToString());
Console.ReadKey();
}
}
}
public static void printString(string[] str)
{
for (int i = 0; i < str.Length; i++)
{
Console.WriteLine(String.IsNullOrEmpty(str[i].ToString()));
}
}
public static Boolean ifPaladine(char[] ar, int start, int end)
{
string reverse = "";
for (int i = ar.Length-1; i >=0; i--)
{
reverse = reverse + ar[i];
}
string c = new string(ar);
if (c.ToLower() == reverse.ToString().ToLower())
return true;
else
return false;
} } }
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace Factorial
{
class Program
{
static void Main(string[] args)
{
char[] str;
string _str = "";
Console.WriteLine("Please enter a string to check Paladin");
str = Console.ReadLine().ToCharArray();
{
if (str.Length == 3)
{
if (ifPaladine(str, 0, str.Length - 1))
{
Console.WriteLine("It Is Paladine");
Console.ReadKey();
}
else
{
Console.WriteLine("Not a paladine");
Console.ReadKey();
} }
else if (str.Length < 3)
{
Console.WriteLine("Invalid input");
return;
}
else if (str.Length > 3)
{
string result = "";
for (int x = 0; x < str.Length - 3; x++)
{
for (int y = x + 3; y <= str.Length; y++)
{
for (int z = x; z < y; z++)
{
_str = _str + str[z];
}
if (ifPaladine(_str.ToCharArray(), 0, _str.Length - 1))
{
result = result + " " + _str;
_str = "";
}
else
_str = "";
} }
if (result.Equals(String.Empty))
Console.WriteLine("No Paladin found");
else
Console.WriteLine(result.ToString());
Console.ReadKey();
} } }
public static void printString(string[] str)
{
for (int i = 0; i < str.Length; i++)
{
Console.WriteLine(String.IsNullOrEmpty(str[i].ToString()));
}
}
public static Boolean ifPaladine(char[] ar, int start, int end)
{
string reverse = "";
for (int i = ar.Length-1; i >=0; i--)
{
reverse = reverse + ar[i];
}
string c = new string(ar);
if (c.ToLower() == reverse.ToString().ToLower())
return true;
else
return false;
} }}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace Factorial
{
class Program
{
static void Main(string[] args)
{
char[] str;
string _str = "";
Console.WriteLine("Please enter a string to check Paladin");
str = Console.ReadLine().ToCharArray();
{
if (str.Length == 3)
{
if (ifPaladine(str, 0, str.Length - 1))
{
Console.WriteLine("It Is Paladine");
Console.ReadKey();
}
else
{
Console.WriteLine("Not a paladine");
Console.ReadKey();
}
}
else if (str.Length < 3)
{
Console.WriteLine("Invalid input");
return;
}
else if (str.Length > 3)
{
string result = "";
for (int x = 0; x < str.Length - 3; x++)
{
for (int y = x + 3; y <= str.Length; y++)
{
for (int z = x; z < y; z++)
{
_str = _str + str[z];
}
if (ifPaladine(_str.ToCharArray(), 0, _str.Length - 1))
{
result = result + " " + _str;
_str = "";
}
else
_str = "";
}
}
if (result.Equals(String.Empty))
Console.WriteLine("No Paladin found");
else
Console.WriteLine(result.ToString());
Console.ReadKey();
}
}
}
public static void printString(string[] str)
{
for (int i = 0; i < str.Length; i++)
{
Console.WriteLine(String.IsNullOrEmpty(str[i].ToString()));
}
}
public static Boolean ifPaladine(char[] ar, int start, int end)
{
string reverse = "";
for (int i = ar.Length-1; i >=0; i--)
{
reverse = reverse + ar[i];
}
string c = new string(ar);
if (c.ToLower() == reverse.ToString().ToLower())
return true;
else
return false;
} } }
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace Factorial
{
class Program
{
static void Main(string[] args)
{
char[] str;
string _str = "";
Console.WriteLine("Please enter a string to check Paladin");
str = Console.ReadLine().ToCharArray();
{
if (str.Length == 3)
{
if (ifPaladine(str, 0, str.Length - 1))
{
Console.WriteLine("It Is Paladine");
Console.ReadKey();
}
else
{
Console.WriteLine("Not a paladine");
Console.ReadKey();
}
}
else if (str.Length < 3)
{
Console.WriteLine("Invalid input");
return;
}
else if (str.Length > 3)
{
string result = "";
for (int x = 0; x < str.Length - 3; x++)
{
for (int y = x + 3; y <= str.Length; y++)
{
for (int z = x; z < y; z++)
{
_str = _str + str[z];
}
if (ifPaladine(_str.ToCharArray(), 0, _str.Length - 1))
{
result = result + " " + _str;
_str = "";
}
else
_str = "";
}
}
if (result.Equals(String.Empty))
Console.WriteLine("No Paladin found");
else
Console.WriteLine(result.ToString());
Console.ReadKey();
}
}
}
public static void printString(string[] str)
{
for (int i = 0; i < str.Length; i++)
{
Console.WriteLine(String.IsNullOrEmpty(str[i].ToString()));
}
}
public static Boolean ifPaladine(char[] ar, int start, int end)
{
string reverse = "";
for (int i = ar.Length-1; i >=0; i--)
{
reverse = reverse + ar[i];
}
string c = new string(ar);
if (c.ToLower() == reverse.ToString().ToLower())
return true;
else
return false;
}
}
}
Solve by dynamic programming in O(n^2)
Lets try with an example
abbaabbac
Starting at position 3 each next character either forms palindromes or it forms none. e.g.
initial string : 'abb' (first 3 chars)
next character added : 'a' (char at pos 4)
Now check string of different length that end at 'a' (next char)
'ba'
'bba'
'abba'
Whenever you encounter a palindrome print it.
Please ignore the logic i shared earlier. Its not dynamic programming but only brute force. Here is the dynamic programming one
Observation: given a palindrome
abcdcba
we see that all substrings of this is also palindrome e.g.
bcdcb
cdc
This is the logic that we are gonna use here. We will also use array A of the same length as the string which will store the length of palindrome that ends at a given char e.g.
abcdcba
A = {0,0,0,0,3,5,7} //we will just see how this array is generated
Q) how to check if there is a palindrome ending in the previous char
Ans) if A[i-1] > 0 then true else false
Also if A[i-1]== 0 then check if the previous char = current char. This will be a 2 length palindrome.
or if the last 2 character and current character form a pallindrome
(Its confusing, but hope i have explained enough)
Lets suppose isPalindrome() is a function that implements the above logic and returns the length of the palindrome ending at a given char
Now start scanning the string.
for each char value = isPalindrome()
if value == 0 A[i] = 0
if value >0 and if current char = char at position i - value
then A[i] = value + 2
In the end scan the array A[i] and find the max length of the palindrome present.
I don't know how to use DP.
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
bool ispalid(string&str)
{
transform(str.begin(), str.end(), str.begin(), ::tolower);
str.erase(remove_if(str.begin(), str.end(), [](char c){return !isalnum(c); }), str.end());
return equal(str.begin(), str.begin() + str.size() / 2, str.rbegin());
}
vector<string> allPalid(string&str)
{
vector<string>result;
string temp;
for (size_t i = 0; i < str.size(); i++)
{
for (size_t j = 0; j <= i; j++)
{
temp = str.substr(j, i - j + 1);
if (ispalid(temp))
result.push_back(temp);
}
}
return result;
}
int main()
{
string str = "abcbafabcba";
vector<string>result;
result = allPalid(str);
for (auto& s : result)
{
cout << s << endl;
}
return 0;
}
void printAllPalendrome(string input){
for(int i =0;i<input.size();i++){
// assume as middle for odd length
int start = i-1;end=i+1;
while(start>= 0 && end<n){
if(input[start] == input[end]){
if(end-start > 3){
cout<<start<<end;
start--;
end++;
}
}
}
// assime as middle for even length
start = i;end=i+1;
while(start>= 0 && end<n){
if(end-start > 3){
cout<<start<<end;
start--;
end++;
}
}
}
}
Hi,
I have an O(n^2) DP solution to find all sub-strings of S of length not smaller than 3 that are palindromes.
Let F[u,v] = 1 if the sub-string of S from u to v (i.e. S[u]..S[v]) is a palindrome, F[u,v] = 0 otherwise.
Then I will need to compute all F[i,j]. Finally, I will check if F[i,i+k] == 1 with k>=3, if so I will output the sub-string from i to i+k.
Formula to compute F[u,v]:
F[u,v] = 3 cases:
1. u == v: F[u,v] = 1;
2. u == v+1: F[u,v] = (S[u] == S[v]);
3. u >= v+2: F[u,v] = (S[u] == S[v]? F[u+1,v-1] : 0)
So, code may look like this:
- entri February 16, 2014for (k=0; k<n; k++) for (i=0; i<n-k; i++){ u = i; v = i+k; F[u,v] = the_formula_above; }