find-maximum-number-of-non-intersecting-substrings

java

python3

python

javascript

typescript

csharp

golang

kotlin

swift

rust

ruby

dart

scala

elixir

erlang

racket

cangjie

bash

mysql

mssql

postgresql

oraclesql

pythondata

Algorithms

You are given a string <code>word</code>.

Return the maximum number of non-intersecting substrings of word that are at least four characters long and start and end with the same letter.

&nbsp;
Example 1:

<div class="example-block">
Input: word = &quot;abcdeafdef&quot;

Output: 2

Explanation:

The two substrings are <code>&quot;abcdea&quot;</code> and <code>&quot;fdef&quot;</code>.
</div>

Example 2:

<div class="example-block">
Input: word = &quot;bcdaaaab&quot;

Output: 1

Explanation:

The only substring is <code>&quot;aaaa&quot;</code>. Note that we cannot also choose <code>&quot;bcdaaaab&quot;</code> since it intersects with the other substring.
</div>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= word.length &lt;= 2 * 105</code></li>
	<li><code>word</code> consists only of lowercase English letters.</li>
</ul>

第 157 场双周赛

biweekly-contest-157

maxSubstrings

高级工程师

Find Maximum Number of Non Intersecting Substrings

Greedy

Hash Table

String

Dynamic Programming

给你一个字符串 <code>word</code>。

返回以&nbsp;首尾字母相同&nbsp;且&nbsp;长度至少为 4&nbsp;的&nbsp;不相交子字符串&nbsp;的最大数量。

子字符串&nbsp;是字符串中连续的&nbsp;非空&nbsp;字符序列。

&nbsp;

示例 1：

<div class="example-block">
输入： word = "abcdeafdef"

输出： 2

解释：

两个子字符串是 <code>"abcdea"</code> 和 <code>"fdef"</code>。
</div>

示例 2：

<div class="example-block">
输入： word = "bcdaaaab"

输出： 1

解释：

唯一的子字符串是 <code>"aaaa"</code>。注意我们&nbsp;不能&nbsp;同时选择 <code>"bcdaaaab"</code>，因为它和另一个子字符串有重叠。
</div>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= word.length &lt;= 2 * 105</code></li>
	<li><code>word</code> 仅由小写英文字母组成。</li>
</ul>