unique-substrings-in-wraparound-string

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

We define the string <code>base</code> to be the infinite wraparound string of <code>&quot;abcdefghijklmnopqrstuvwxyz&quot;</code>, so <code>base</code> will look like this:

<ul>
	<li><code>&quot;...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd....&quot;</code>.</li>
</ul>

Given a string <code>s</code>, return the number of unique non-empty substrings of <code>s</code> are present in <code>base</code>.

&nbsp;
Example 1:

<pre>
Input: s = &quot;a&quot;
Output: 1
Explanation: Only the substring &quot;a&quot; of s is in base.
</pre>

Example 2:

<pre>
Input: s = &quot;cac&quot;
Output: 2
Explanation: There are two substrings (&quot;a&quot;, &quot;c&quot;) of s in base.
</pre>

Example 3:

<pre>
Input: s = &quot;zab&quot;
Output: 6
Explanation: There are six substrings (&quot;z&quot;, &quot;a&quot;, &quot;b&quot;, &quot;za&quot;, &quot;ab&quot;, and &quot;zab&quot;) of s in base.
</pre>

&nbsp;
Constraints:

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

findSubstringInWraproundString

Unique Substrings in Wraparound String

String

Dynamic Programming

定义字符串&nbsp;<code>base</code>&nbsp;为一个&nbsp;<code>"abcdefghijklmnopqrstuvwxyz"</code>&nbsp;无限环绕的字符串，所以&nbsp;<code>base</code>&nbsp;看起来是这样的：

<ul>
	<li><code>"...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd...."</code>.</li>
</ul>

给你一个字符串&nbsp;<code>s</code> ，请你统计并返回&nbsp;<code>s</code>&nbsp;中有多少&nbsp;不同非空子串&nbsp;也在&nbsp;<code>base</code>&nbsp;中出现。

&nbsp;

示例&nbsp;1：

<pre>
输入：s = "a"
输出：1
解释：字符串 s 的子字符串 "a" 在 base 中出现。
</pre>

示例 2：

<pre>
输入：s = "cac"
输出：2
解释：字符串 s 有两个子字符串 ("a", "c") 在 base 中出现。
</pre>

示例 3：

<pre>
输入：s = "zab"
输出：6
解释：字符串 s 有六个子字符串 ("z", "a", "b", "za", "ab", and "zab") 在 base 中出现。
</pre>

&nbsp;

提示：

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