maximum-number-of-non-overlapping-palindrome-substrings

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You are given a string <code>s</code> and a positive integer <code>k</code>.

Select a set of non-overlapping substrings from the string <code>s</code> that satisfy the following conditions:

<ul>
	<li>The length of each substring is at least <code>k</code>.</li>
	<li>Each substring is a palindrome.</li>
</ul>

Return the maximum number of substrings in an optimal selection.

A substring is a contiguous sequence of characters within a string.

&nbsp;
Example 1:

<pre>
Input: s = &quot;abaccdbbd&quot;, k = 3
Output: 2
Explanation: We can select the substrings underlined in s = &quot;abaccdbbd&quot;. Both &quot;aba&quot; and &quot;dbbd&quot; are palindromes and have a length of at least k = 3.
It can be shown that we cannot find a selection with more than two valid substrings.
</pre>

Example 2:

<pre>
Input: s = &quot;adbcda&quot;, k = 2
Output: 0
Explanation: There is no palindrome substring of length at least 2 in the string.
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= k &lt;= s.length &lt;= 2000</code></li>
	<li><code>s</code> consists of lowercase English letters.</li>
</ul>

maxPalindromes

Maximum Number of Non-overlapping Palindrome Substrings

Longest Palindromic Substring

longest-palindromic-substring

最长回文子串

Palindrome Partitioning

palindrome-partitioning

分割回文串

Palindrome Partitioning II

palindrome-partitioning-ii

分割回文串 II

Palindrome Partitioning III

palindrome-partitioning-iii

分割回文串 III

Maximum Number of Non-Overlapping Substrings

maximum-number-of-non-overlapping-substrings

最多的不重叠子字符串

Palindrome Partitioning IV

palindrome-partitioning-iv

分割回文串 IV

Greedy

Two Pointers

String

Dynamic Programming

给你一个字符串 <code>s</code> 和一个 正 整数 <code>k</code> 。

从字符串 <code>s</code> 中选出一组满足下述条件且 不重叠 的子字符串：

<ul>
	<li>每个子字符串的长度 至少 为 <code>k</code> 。</li>
	<li>每个子字符串是一个 回文串 。</li>
</ul>

返回最优方案中能选择的子字符串的 最大 数目。

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

&nbsp;

示例 1 ：

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

示例 2 ：

<pre>
输入：s = "adbcda", k = 2
输出：0
解释：字符串中不存在长度至少为 2 的回文子字符串。
</pre>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= k &lt;= s.length &lt;= 2000</code></li>
	<li><code>s</code> 仅由小写英文字母组成</li>
</ul>