• 首页 首页 icon
  • 工具库 工具库 icon
    • IP查询 IP查询 icon
  • 内容库 内容库 icon
    • 快讯库 快讯库 icon
    • 精品库 精品库 icon
    • 问答库 问答库 icon
  • 更多 更多 icon
    • 服务条款 服务条款 icon

算法题2472. 不重叠回文子字符串的最大数目

武飞扬头像
kangbin825
帮助1

题目:

给你一个字符串 s 和一个 正 整数 k 。

从字符串 s 中选出一组满足下述条件且 不重叠 的子字符串:

每个子字符串的长度 至少 为 k 。
每个子字符串是一个 回文串 。
返回最优方案中能选择的子字符串的 最大 数目。

子字符串 是字符串中一个连续的字符序列。

示例 1 :

输入:s = “abaccdbbd”, k = 3
输出:2
解释:可以选择 s = “abaccdbbd” 中斜体加粗的子字符串。“aba” 和 “dbbd” 都是回文,且长度至少为 k = 3 。
可以证明,无法选出两个以上的有效子字符串。
示例 2 :

输入:s = “adbcda”, k = 2
输出:0
解释:字符串中不存在长度至少为 2 的回文子字符串。

提示:

1 <= k <= s.length <= 2000
s 仅由小写英文字母组成

java代码:

class Solution {
    public int maxPalindromes(String S, int k) {
        var s = S.toCharArray();
        var n = s.length;
        var f = new int[n   1];
        for (var i = 0; i < 2 * n - 1;   i) {
            int l = i / 2, r = l   i % 2; // 中心扩展法
            f[l   1] = Math.max(f[l   1], f[l]);
            for (; l >= 0 && r < n && s[l] == s[r]; --l,   r)
                if (r - l   1 >= k) {
                    f[r   1] = Math.max(f[r   1], f[l]   1);
                    break;
                }
        }
        return f[n];
    }
}

这篇好文章是转载于:学新通技术网

  • 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
  • 本站站名: 学新通技术网
  • 本文地址: /boutique/detail/tanhhhjchi
系列文章
更多 icon
同类精品
更多 icon
继续加载