longest-ideal-subsequence

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> consisting of lowercase letters and an integer <code>k</code>. We call a string <code>t</code> ideal if the following conditions are satisfied:

<ul>
	<li><code>t</code> is a subsequence of the string <code>s</code>.</li>
	<li>The absolute difference in the alphabet order of every two adjacent letters in <code>t</code> is less than or equal to <code>k</code>.</li>
</ul>

Return the length of the longest ideal string.

A subsequence is a string that can be derived from another string by deleting some or no characters without changing the order of the remaining characters.

Note that the alphabet order is not cyclic. For example, the absolute difference in the alphabet order of <code>&#39;a&#39;</code> and <code>&#39;z&#39;</code> is <code>25</code>, not <code>1</code>.

&nbsp;
Example 1:

<pre>
Input: s = &quot;acfgbd&quot;, k = 2
Output: 4
Explanation: The longest ideal string is &quot;acbd&quot;. The length of this string is 4, so 4 is returned.
Note that &quot;acfgbd&quot; is not ideal because &#39;c&#39; and &#39;f&#39; have a difference of 3 in alphabet order.</pre>

Example 2:

<pre>
Input: s = &quot;abcd&quot;, k = 3
Output: 4
Explanation: The longest ideal string is &quot;abcd&quot;. The length of this string is 4, so 4 is returned.
</pre>

&nbsp;
Constraints:

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

longestIdealString

Longest Ideal Subsequence

Longest Increasing Subsequence

longest-increasing-subsequence

最长递增子序列

Hash Table

String

Dynamic Programming

给你一个由小写字母组成的字符串 <code>s</code> ，和一个整数 <code>k</code> 。如果满足下述条件，则可以将字符串 <code>t</code> 视作是 理想字符串 ：

<ul>
	<li><code>t</code> 是字符串 <code>s</code> 的一个子序列。</li>
	<li><code>t</code> 中每两个 相邻 字母在字母表中位次的绝对差值小于或等于 <code>k</code> 。</li>
</ul>

返回 最长 理想字符串的长度。

字符串的子序列同样是一个字符串，并且子序列还满足：可以经由其他字符串删除某些字符（也可以不删除）但不改变剩余字符的顺序得到。

注意：字母表顺序不会循环。例如，<code>'a'</code> 和 <code>'z'</code> 在字母表中位次的绝对差值是 <code>25</code> ，而不是 <code>1</code> 。

&nbsp;

示例 1：

<pre>
输入：s = "acfgbd", k = 2
输出：4
解释：最长理想字符串是 "acbd" 。该字符串长度为 4 ，所以返回 4 。
注意 "acfgbd" 不是理想字符串，因为 'c' 和 'f' 的字母表位次差值为 3 。</pre>

示例 2：

<pre>
输入：s = "abcd", k = 3
输出：4
解释：最长理想字符串是 "abcd" ，该字符串长度为 4 ，所以返回 4 。
</pre>

&nbsp;

提示：

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