## Interview Question

Backend Developers**Team:**3

**Country:**India

This is how I'd go about it,

K will denote the level of the string in the reverse order 0 will be the last

based on the level iterate from end of the previous level to N-level

the rest of the string from current end to the last will be recursively solved

if the current substring is palindrome send 1 (c+1) to the next level

the c will be added to count at the end will have the no of palindromes for the current split

```
static Scanner sc = new Scanner(System.in);
static String input;
static int count = 0;
static int n;
public static void main(String[] args) {
System.out.print("Enter N and K : ");
n = sc.nextInt();
var k = sc.nextInt();
input = sc.nextLine();
System.out.print("Enter the String : ");
input = sc.nextLine();
checkPalin(0, 0, k);
System.out.println("The count of Palindrome in " + input + " = " + count);
}
private static void checkPalin(int c, int start, int lvl) {
if (lvl > 0)
for (int end = start + 1; end <= n - lvl; end++) {
int tmp = 0;
if (isPalin(start, end)) tmp = 1;
checkPalin(c + tmp, end, lvl - 1);
}
if (lvl == 0) {
if (isPalin(start, n)) c += 1;
count += c;
}
}
private static boolean isPalin(int start, int end) {
for (int i = 0; i < (end - start) / 2; i++)
if (input.charAt(start + i) != input.charAt(end - i - 1))
return false;
return true;
}
```

We could use dynamic programming. Something like this:

```
def count(s,k):
dp1 = [[0]*(len(s)+1)
for _ in range(k+1)]
dp2 = [[0]*(len(s)+1)
for _ in range(k+1)]
for i in range(len(s)):
for j in range(i+1):
z = s[j:i+1]
p = [0,1][z == z[::-1]]
if j == 0:
dp1[0][i+1] = p
dp2[0][i+1] = 1
for c in range(1, min(k,j)+1):
w = dp1[c-1][j]
y = dp2[c-1][j]
dp1[c][i+1] += w + p*y
dp2[c][i+1] += y
return dp1[k][len(s)]
print count ('aabbc', 2)
```

public static void main(String[] args)

{

int cuts = 2;

String str = "aabbc";

String[] cutted = new String[cuts+1];

for(int i=0;i<=cuts;i++)

{

if(i==cuts)

cutted[i] = str.substring(i);

else

cutted[i] = str.substring(i,i+1);

}

cutString(cutted, cuts, cuts, 0);

}

static void cutString(String[] cutted, int cuts, int cp, int palinCount)

{

System.out.println(Arrays.deepToString(cutted) + " : " + (palinCount+=palinCount(cutted)));

if(cutted[cp].length()>1)

{

cutted[cp-1] = cutted[cp-1]+cutted[cp].charAt(0);

cutted[cp] = cutted[cp].substring(1);

cutString(cutted, cuts, cp, palinCount);

}

else

{

cp--;

if(cp>0)

cutString(cutted, cuts, cp, palinCount);

}

}

static int palinCount(String[] strArr)

{

int count=0;

for(String str:strArr)

{

if(checkPali(str)) count++;

}

return count;

}

Please Send Me Expected Coding Assesment Questions List With Solutions In Java By Today As I Need An Urgent Help From You. Please Reply My Comment By Today On My Whats App Contact 9557041140 And Email ID jatinbhardwaaj18@gmail.com. Please Reply My Query By Today As I Need An Urgent Help From You For Placement And Internships So Do Me A Favour.

Type: Recursion + Loop Problem

Loop on String Length. That is, 1 to MAX(CEILING(N/K), (N-K)) (inclusive)

- Minimum String Length is 1 because non-empty string

- Maximum String Length is a bit tricky

-- K cuts would result in K+1 Strings

-- Case-A: Cuts are equal in size, so max str len is (N/K) (ceiled)

-- Case-B: Cuts are not equal. Max length of (K+1)th string is (N-K) where other K strings are of min len 1

Recursion on String

Psuedo-Code:

- Laxmi Narsimha Rao Oruganti November 26, 2018