split-a-string-into-the-max-number-of-unique-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

Given a string&nbsp;<code>s</code><var>,</var>&nbsp;return the maximum&nbsp;number of unique substrings that the given string can be split into.

You can split string&nbsp;<code>s</code> into any list of&nbsp;non-empty substrings, where the concatenation of the substrings forms the original string.&nbsp;However, you must split the substrings such that all of them are unique.

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

&nbsp;
Example 1:

<pre>
Input: s = &quot;ababccc&quot;
Output: 5
Explanation: One way to split maximally is [&#39;a&#39;, &#39;b&#39;, &#39;ab&#39;, &#39;c&#39;, &#39;cc&#39;]. Splitting like [&#39;a&#39;, &#39;b&#39;, &#39;a&#39;, &#39;b&#39;, &#39;c&#39;, &#39;cc&#39;] is not valid as you have &#39;a&#39; and &#39;b&#39; multiple times.
</pre>

Example 2:

<pre>
Input: s = &quot;aba&quot;
Output: 2
Explanation: One way to split maximally is [&#39;a&#39;, &#39;ba&#39;].
</pre>

Example 3:

<pre>
Input: s = &quot;aa&quot;
Output: 1
Explanation: It is impossible to split the string any further.
</pre>

&nbsp;
Constraints:

<ul>
	<li>
	<code>1 &lt;= s.length&nbsp;&lt;= 16</code>
	</li>
	<li>
	<code>s</code> contains&nbsp;only lower case English letters.
	</li>
</ul>

maxUniqueSplit

Split a String Into the Max Number of Unique Substrings

Hash Table

String

Backtracking

给你一个字符串 <code>s</code> ，请你拆分该字符串，并返回拆分后唯一子字符串的最大数目。

字符串 <code>s</code> 拆分后可以得到若干 非空子字符串 ，这些子字符串连接后应当能够还原为原字符串。但是拆分出来的每个子字符串都必须是 唯一的 。

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

&nbsp;

示例 1：

<pre>输入：s = &quot;ababccc&quot;
输出：5
解释：一种最大拆分方法为 [&#39;a&#39;, &#39;b&#39;, &#39;ab&#39;, &#39;c&#39;, &#39;cc&#39;] 。像 [&#39;a&#39;, &#39;b&#39;, &#39;a&#39;, &#39;b&#39;, &#39;c&#39;, &#39;cc&#39;] 这样拆分不满足题目要求，因为其中的 &#39;a&#39; 和 &#39;b&#39; 都出现了不止一次。
</pre>

示例 2：

<pre>输入：s = &quot;aba&quot;
输出：2
解释：一种最大拆分方法为 [&#39;a&#39;, &#39;ba&#39;] 。
</pre>

示例 3：

<pre>输入：s = &quot;aa&quot;
输出：1
解释：无法进一步拆分字符串。
</pre>

&nbsp;

提示：

<ul>
	<li>
	<code>1 &lt;= s.length&nbsp;&lt;= 16</code>
	</li>
	<li>
	<code>s</code> 仅包含小写英文字母
	</li>
</ul>