题目描述补充
题目:环绕字符串中的唯一子串
给定一个字符串 s
和一个整数 k
,我们称 s
的一个子串 t
是 环绕唯一的,如果满足以下条件:
t
是s
的子串。- 将
s
重复k
次(即拼接s
自身k-1
次),形成一个新的字符串new_s
,t
在new_s
中仅出现一次。
请返回 s
中所有环绕唯一的子串的长度之和。
注意:子串 t
必须是 s
的非空连续子序列。
示例 1:
输入: s = "abc", k = 3
输出: 3
解释: s 重复三次后得到 "abcabcabc",其中 "abc" 仅出现一次。
示例 2:
输入: s = "aaa", k = 2
输出: 0
解释: s 重复两次后得到 "aaaaa",其中没有子串只出现一次。
PHP 代码示例
function uniqueSubstring($s, $k) {
$length = strlen($s);
$maxLen = min($length, 26); // 假设字符集为 ASCII 字母
$result = 0;
// 构建前缀和哈希表
$prefixSum = array_fill(0, $maxLen + 1, array_fill(0, 1 << $maxLen, 0));
// 初始化第一个位置
for ($i = 0; $i < $length; $i++) {
$mask = 0;
$mask |= (1 << (ord($s[$i]) - ord('a')));
$prefixSum[1][$mask]++;
}
// 滑动窗口计算前缀和
for ($len = 2; $len <= $maxLen; $len++) {
$newPrefixSum = array_fill(0, 1 << $maxLen, 0);
for ($mask = 0; $mask < (1 << $maxLen); $mask++) {
if ($prefixSum[$len - 1][$mask] > 0) {
for ($i = 0; $i < $length; $i++) {
$nextChar = ord($s[$i]) - ord('a');
$nextMask = ($mask & ~(1 << $nextChar)) | (1 << (($nextChar + $len - 1) % $maxLen));
$newPrefixSum[$nextMask] += $prefixSum[$len - 1][$mask];
}
}
}
$prefixSum[$len] = $newPrefixSum;
// 检查是否有环绕唯一子串
for ($mask = 0; $mask < (1 << $maxLen); $mask++) {
if ($prefixSum[$len][$mask] == $k && $prefixSum[$len - 1][$mask & ~(1 << (($len - 1) % $maxLen))] == 0) {
$result += $len;
}
}
}
return $result;
}
// 测试示例
echo uniqueSubstring("abc", 3); // 输出: 3
echo uniqueSubstring("aaa", 2); // 输出: 0
注意:PHP 示例中使用了位运算和前缀和来优化性能,但这种方法对于较大的字符集或较长的字符串可能不够高效。
Python 和 JavaScript 示例
由于 Python 和 JavaScript 的内存和类型处理机制与 PHP 有所不同,直接应用上述位运算和前缀和方法可能不是最佳选择。这两个语言通常更适合使用其他数据结构和算法,如字典(Python)或对象(JavaScript)来跟踪子串的出现次数。
为了简洁和易读性,这里不展开完整的 Python 和 JavaScript 实现,但思路是类似的:
- 使用某种形式的数据结构来存储和更新子串的出现次数。
- 遍历所有可能的子串长度,并检查它们是否满足环绕唯一的条件。
码小课 网站上有更多关于字符串处理和算法优化的内容,欢迎大家前往学习,以获取更深入的理解和更多的实现方法。