Interview Question
Backend DevelopersTeam: 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