Comment on page
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
给定一个字符串,让求出最多可以切成分块的回文,每一个切分可以是一个子字符串,或者单个字符。
例如,
"aaaaaa"
, 可以切分成 "aaa)(aaa)" - 2
, 但是这里要求最多分块, 这样就是最多的"(a)(a)(a)(a)(a)(a)" - 6
分析, 满足回文字符串的要求是,从前读和从后读是一样的, 例如,
"aba", "anna","madam"
等那么这里就可以分别从前
(l)
和从后(r)
扫描,l
和 r
记录前后扫描的index
, 然后用pre_l
and pre_r
记录前一次扫描到的可以分块的回文位置,如果子字符串相同(substr(pre_l, l + 1) 这里包含边界),结果 +2,继续扫描。
如果最后剩余一个(奇数个chunk), 那么直接结果 +1, 否则偶数个chunk, 直接返回结果
例如:
"volvolvo"

alt text
时间复杂度:
O(N^2) - N is the s length, s.substring()时间复杂度是O(n)
空间复杂度:
O(1) - 没有额外的空间
从解法一中我们可以看到
palindome
左右对称, 所以可以从左和右,用递归求解。如下图例子, 可以从左起子字符串匹配最右起的子字符串。绿色框框,如果匹配, 递归的计算最长的回文,即每次碰到回文就计算 +2, 直到最后字符串中没有匹配的回文,或者是匹配到最后, 退出, 返回结果。
例如:
"volvolvo"

alt text
解法一
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;
}
}
Last modified 4yr ago