S
S
Study Notes
Search
K
Comment on page

# chunked-palindrome

## Chunked Palindrome

### 题目描述

Normal palindrome is defined as a string that reads the same backwards as forwards, for example "abccba".
Chunked palindrome is defined as a string that you can split into chunks and it will form a palindrome.
For example, "volvo". You can split it into (vo)(l)(vo). Let A = "vo", B = "l", so the original string is ABA which is a palindrome.
Given a string str, find the maximum number of chunks we can split that string to get a chuncked palindrome.
Example 1:
Input: "valve"
Output: 1
Explanation: You can't split it into multiple chunks so just return 1 (valve)
Example 2:
Input: "voabcvo"
Output: 3
Explanation: (vo)(abc)(vo)
Example 3:
Input: "vovo"
Output: 2
Explanation: (vo)(vo)
Example 4:
Input: "volvolvo"
Output: 5
Explanation: (vo)(l)(vo)(l)(vo)
Example 5:
Input: "volvol"
Output: 2
Explanation: (vol)(vol)
Example 6:
Input: "aaaaaa"
Output: 6
Explanation: We can split it into (aaa)(aaa), but the optimal split should be (a)(a)(a)(a)(a)(a)
Questions from the same interview:
Product of K consecutive numbers

alt text

alt text

## 代码 （Java）

class ChunkedPalindrom {
public static int maxChunkedPalindrome2(String s) {
if (s == null || s.length() == 0) return 0;
int l = 0;
int r = s.length() - 1;
int max = 0;
int preL = l;
int preR = r;
while (l < r) {
String prefix = s.substring(preL, l + 1); // include right
String sufix = s.substring(r, preR + 1);
if (prefix.equals(sufix)) {
preL = l + 1;
preR = r - 1;
max += 2;
}
l++;
r--;
}
if (preL <= preR) max++;
System.out.println("max chunk palindrom: " + max);
return max;
}
}

class ChunkedPalindrome {
public static int maxChunkedPalindrome(String s) {
if (s == null || s.length() == 0) return 0;
return helper(s, 0, 0, s);
}
private static int helper(String curr, int count, int len, String s) {
// no substring left, return current count
if (curr == null || curr.isEmpty()) return count;
if (curr.length() <= 1) {
if (count != 0 && s.length() - len <= 1) {
return count + 1;
} else return 1;
}
int currLen = curr.length();
// get left and right substring and compare
for (int i = 0; i < currLen / 2; i++) {
String left = curr.substring(0, i + 1);
String right = curr.substring(currLen - 1 - i, currLen);
if (left.equals(right)) {
// if left and right match, then continue match the rest substring (s - left - right)
return helper(curr.substring(i + 1, currLen - 1 - i),
count + 2, len + (i + 1) * 2, s);
}
}
return count + 1;
}
}