Amazon Interview Question
SDE1sCountry: United States
Interview Type: Written Test
subString function omits last character in the string, update it to following:
String s = str.substring(i , j+1);
The complexity of your solution is O(n^3)
Here is a solution O(n+P) where P is the total size of all palindromes.
void print_palindromes(const std::string& s)
{
auto n = s.length();
for (auto i = 0; i < n; ++i)
{
// odd palindrome
auto j = i;
auto k = i;
while (j >= 0 && k < n)
{
if (s[j] != s[k]) break;
std::cout << s.substr(j,j-k+1) << std::endl;
--j; ++k;
}
// even palindrome
j = i-1;
k = i;
while (j >= 0 && k < n)
{
if (s[j] != s[k]) break;
std::cout << s.substr(j,j-k+1) << std::endl;
--j; ++k;
}
}
}
s = our string
Keep two pointers. p1 is always one element behind p2. Every iteration, both are incremented. We check if s[p2] == s[p1] or s[p1-1]. If so, we know that we have a palindrome in some form, so we start recording the string with 2 pointers- iterate outwards until the palindrome ends and record all of the "visited" strings into an output table.
For example with the String "4racecarses", p1 and p2 are incremented until p2 = 5 and p1 = 4, s[p2] = s[p1-1]. Now, we iterate outwards: cec -> aceca -> racecar -> stop at 4racecars since the outward pointers won't match.
Back to the original loop, p2 is then at 6. Until it gets to the final element, it won't find a potential palindrome
In the end, add all single characters to the list
package com.practice.algo.and.ds.dp;
public class FindAllThePalindromesInString {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
String str = "Mississippi";
FindAllThePalindromesInString f = new FindAllThePalindromesInString();
f.getAllPalindromes(str);
}
private void getAllPalindromes(String str) {
// TODO Auto-generated method stub
int[][] dp = new int[str.length()][str.length()];
//Mark one length string as palindromes
for(int i=0;i<str.length();i++){
dp[i][i] = 1;
}
//Mark two length string as palindromes if both start and end are same
for(int i=0;i<str.length()-1;i++){
if(str.charAt(i)==str.charAt(i+1))
dp[i][i+1] = 1;
}
for(int jump =2 ;jump<str.length();jump++){
for(int i=0;i<str.length()-jump;i++){
int j = i+jump;
if(str.charAt(i)==str.charAt(j)){
if(dp[i+1][j-1]>=1){
dp[i][j] = dp[i+1][j-1]>=1?(1+dp[i+1][j-1]):0;
for(int k=i;k<=j;k++){
System.out.print(str.charAt(k));
}
System.out.println();
}
}else{
dp[i][j] = 0;
}
}
}
}
}
package com.practice.algo.and.ds.dp;
public class FindAllThePalindromesInString {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
String str = "Mississippi";
FindAllThePalindromesInString f = new FindAllThePalindromesInString();
f.getAllPalindromes(str);
}
private void getAllPalindromes(String str) {
// TODO Auto-generated method stub
int[][] dp = new int[str.length()][str.length()];
//Mark one length string as palindromes
for(int i=0;i<str.length();i++){
dp[i][i] = 1;
}
//Mark two length string as palindromes if both start and end are same
for(int i=0;i<str.length()-1;i++){
if(str.charAt(i)==str.charAt(i+1))
dp[i][i+1] = 1;
}
for(int jump =2 ;jump<str.length();jump++){
for(int i=0;i<str.length()-jump;i++){
int j = i+jump;
if(str.charAt(i)==str.charAt(j)){
if(dp[i+1][j-1]>=1){
dp[i][j] = dp[i+1][j-1]>=1?(1+dp[i+1][j-1]):0;
for(int k=i;k<=j;k++){
System.out.print(str.charAt(k));
}
System.out.println();
}
}else{
dp[i][j] = 0;
}
}
}
}
}
First you start by populating a two-dimensional array with two arrays of objects, one for single characters (index 0, 1) and the other for double characters (index 0, 2), with the following information:
the palindrome itself and
the position in the string of the start of the palindrome.
From there you iterate through the arrays, starting at N = 3, with each step N starting off of array N - 2 (which starts at 0, N - 2 in the 2D array). For each palindrome in the array for the current step, check the string for if charAt(palindromeStart - 1) == charAt(palindromeStart + N), adding the substring for those positions to the Nth array in the 2D array. Repeat until the arrays of indices 0, N - 1 and 0, N - 2 are empty, or N > the total length of the string.
For a visual example, the strings "Mississippi" and "racecar" would give you
[ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ]
[M][i][s][s][i][s][s][i][p][p][i]
[ss][ss][pp]
[sis]
[issi][issi][ippi]
[ssiss]
[]EMPTY
[ississi]
and
[ ][ ][ ][ ][ ][ ][ ]
[r][a][c][e][c][a][r]
[ ]EMPTY
[cec]
[ ]EMPTY
[aceca]
[ ]EMPTY
[racecar]
Worst case complexity would be O(n^2), for a string of only identical characters, with an average case of O(n).
For a palindrome, it should have a pattern like this:
aa
aXa
where 'a' is a set of palindromic characters. e.g.
abba
abXba .. and so on.
An algo could be:
1. find a character that matches with another one. We can use a 'diff' that goes from 1 to length/2. If the characters at i-th and (i+diff)-th position matches, it's a potential palindrome.
2. if the diff==1, the characters are side by side, like 'ss', which is a palindrome anyway.
3. if the diff>1, check the characters from both sides, up to the middle of the substring. if it matches from both sides, it's a palindrome.
Something like this (elaborated with sysouts) ... can be tuned, though.
package com.mishra.partha.prep.simple;
public class Palindromes {
public static void main(String[] args){
String str="mississipi";
System.out.println("Number of Palindromes found= "+getPalindromes(str));
}
static int getPalindromes(String s){
int count=0;
for(int diff=1; diff < s.length()/2; diff++){
for(int i=0; i<s.length()-diff; i++){
if(s.charAt(i)==s.charAt(i+diff)){
count+= checkPalindromic(s,i,diff);
}
}
}
return count;
}
private static int checkPalindromic(String s, int i, int diff) {
int end=i+diff;
if (diff >1){
for(int x=0; x<diff; x++){
if(s.charAt(i+x)!=s.charAt(end-x)){
return 0;
}
}
}
System.out.println("Found Palindrome: "+s.substring(i, end+1));
return 1;
}
}
Output comes as
Found Palindrome: ss
Found Palindrome: ss
Found Palindrome: sis
Found Palindrome: ipi
Found Palindrome: issi
Found Palindrome: issi
Found Palindrome: ssiss
Number of Palindromes found= 7
Actually, on the last mississipi (missing a 'p') example, there should be one more palidrome... "ississi".
If Spelled correctly, it should have found 9... including
"ippi" and "pp"
Simple solution based on using two pointers (p1 and p2):
For odd palindromes
1) At each index i of the String s, set p1 to i - 1 and p2 to i + 1.
2) If s[p1] == s[p2], then we have a palindrome. Continue to next index until we reach boundary of string and set p1 = p1 - 1 and p2 = p2 + 1.
For even palindromes, it is the same as above but start with p1 = i instead of i - 1.
public static Set<String> findAllPalindromes(String string) {
Set<String> palindromes = new HashSet<String>();
char[] stringAsCharArray = string.toCharArray();
//Odd palindromes
for (int i=0; i < string.length(); i++) {
int p1 = i - 1;
int p2 = i + 1;
while (p1 >= 0 && p2 < string.length()) {
if (stringAsCharArray[p1] == stringAsCharArray[p2]) {
palindromes.add(string.substring(p1, p2 + 1));
} else {
break;
}
p1 = p1 - 1;
p2 = p2 + 1;
}
}
//Even palindromes
for (int i=0; i < string.length(); i++) {
int p1 = i;
int p2 = i + 1;
while (p1 >= 0 && p2 < string.length()) {
if (stringAsCharArray[p1] == stringAsCharArray[p2]) {
palindromes.add(string.substring(p1, p2 + 1));
} else {
break;
}
p1 = p1 - 1;
p2 = p2 + 1;
}
}
return palindromes;
}
Check even/odd for every centered palindromes:
#include <stdio.h>
#include <string.h>
int main(void)
{
int i, j;
char str[] = "mississipi";
int n = (int)strlen(str);
int even, odd;
for (i = 0; i < n; i++) {
even = 1;
odd = 1;
for (j = 0; even || odd; j++) {
if (i - j < 0)
break;
if (i + j >= n)
break;
if (str[i + j] != str[i - j]) {
odd = 0;
} else if (odd) {
printf("%.*s\n", 2 * j + 1, str + i - j);
}
if (i + 1 + j >= n)
continue;
if (str[i + 1 + j] != str[i - j]) {
even = 0;
} else if (even) {
printf("%.*s\n", 2 * (j + 1), str + i - j);
}
}
}
return 0;
}
public static void findAllPalindrome2(String str){
List<String> result = new ArrayList<String>();
for(int i=0;i<str.length();i++){
getAllCombinations(result,str,i,str.length()-1);
}
for(String s:result){
System.out.println(s);
}
}
private static void getAllCombinations(List<String> result, String str,
int startIndex,int endIndex) {
if(endIndex<=startIndex){
return ;
}
if(str.charAt(startIndex)==str.charAt(endIndex)){
if(checkIfPalindrome(str,startIndex,endIndex)){
//add to the result;
result.add(str.substring(startIndex,endIndex+1));
}
}
getAllCombinations(result, str, startIndex, endIndex-1);
}
private static boolean checkIfPalindrome(String str, int startIndex,
int endIndex) {
while(startIndex<=endIndex && startIndex<str.length() && endIndex>=0){
if(str.charAt(startIndex++)!=str.charAt(endIndex--)){
return false;
}
}
return true;
}
Nice and concise :)
void PrintPalindromes(char* pStr)
{
char* pStart = pStr-1, *pEnd;
while (*(pEnd = ++pStart)){
fail: while ((pEnd = strchr(pEnd+1, *pStart)) != NULL){
for (int i = 0; (i < (pEnd-pStart+1)/2); i++)
if (pStart[i] != pEnd[-i]) goto fail;
std::cout << std::string(pStart, pEnd-pStart+1) << "\n";
}
}
}
public static List<String> findPal(String str) {
int global = 0, left = 0, right = 0;
List<String> res = new ArrayList<String>();
while (global < str.length()) {
res.add(new String(new char[]{str.charAt(global)}));
right++;
while (right < str.length() && str.charAt(global) == str.charAt(right)) {
res.add(str.substring(global, right + 1).intern());
right++;
}
left--;
while (right < str.length() && left >= 0) {
if (str.charAt(left) == str.charAt(right)) {
res.add(str.substring(left, right + 1).intern());
} else {
break;
}
right++;
left--;
}
global++;
right = global;
left = global;
}
return res;
}
public static void findAllPalindromes(String s){
if(s.isEmpty() || s==null) throw new IllegalArgumentException();
int n=s.length();
boolean[][] res= new boolean[n][n];
List<String> palindromes= new LinkedList<String>();
for(int i=0;i<n;i++){
res[i][i]=true;
palindromes.add(Character.toString(s.charAt(i)));
}
for(int cl=2;cl<=n;cl++){
for(int i=0;i<n-cl+1;i++){
int j=i+cl-1;
if(s.charAt(i)==s.charAt(j) && cl==2){
palindromes.add(s.substring(i,j));
res[i][j]=true;
}
else if(s.charAt(i)==s.charAt(j) ){
res[i][j]=(res[i+1][j-1])?true:false;
if(res[i][j] && j==n-1){
palindromes.add(s.substring(i));
}
else if(res[i][j]){
palindromes.add(s.substring(i,j+1));
}
}
else{
res[i][j]=false;
}
}
}
for(String pal: palindromes){
System.out.println(pal);
}
}
public static void findAllPalindromes(String s){
if(s.isEmpty() || s==null) throw new IllegalArgumentException();
int n=s.length();
boolean[][] res= new boolean[n][n];
List<String> palindromes= new LinkedList<String>();
for(int i=0;i<n;i++){
res[i][i]=true;
palindromes.add(Character.toString(s.charAt(i)));
}
for(int cl=2;cl<=n;cl++){
for(int i=0;i<n-cl+1;i++){
int j=i+cl-1;
if(s.charAt(i)==s.charAt(j) && cl==2){
palindromes.add(s.substring(i,j));
res[i][j]=true;
}
else if(s.charAt(i)==s.charAt(j) ){
res[i][j]=(res[i+1][j-1])?true:false;
if(res[i][j] && j==n-1){
palindromes.add(s.substring(i));
}
else if(res[i][j]){
palindromes.add(s.substring(i,j+1));
}
}
else{
res[i][j]=false;
}
}
}
for(String pal: palindromes){
System.out.println(pal);
}
}
}
- Santhosh February 07, 2015