## 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)
```

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