longest-subsequence-repeated-k-times

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> of length <code>n</code>, and an integer <code>k</code>. You are tasked to find the longest subsequence repeated <code>k</code> times in string <code>s</code>.

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.

A subsequence <code>seq</code> is repeated <code>k</code> times in the string <code>s</code> if <code>seq * k</code> is a subsequence of <code>s</code>, where <code>seq * k</code> represents a string constructed by concatenating <code>seq</code> <code>k</code> times.

<ul>
	<li>For example, <code>&quot;bba&quot;</code> is repeated <code>2</code> times in the string <code>&quot;bababcba&quot;</code>, because the string <code>&quot;bbabba&quot;</code>, constructed by concatenating <code>&quot;bba&quot;</code> <code>2</code> times, is a subsequence of the string <code>&quot;bababcba&quot;</code>.</li>
</ul>

Return the longest subsequence repeated <code>k</code> times in string <code>s</code>. If multiple such subsequences are found, return the lexicographically largest one. If there is no such subsequence, return an empty string.

&nbsp;
Example 1:
<img alt="example 1" src="https://assets.leetcode.com/uploads/2021/08/30/longest-subsequence-repeat-k-times.png" style="width: 457px; height: 99px;" />
<pre>
Input: s = &quot;letsleetcode&quot;, k = 2
Output: &quot;let&quot;
Explanation: There are two longest subsequences repeated 2 times: &quot;let&quot; and &quot;ete&quot;.
&quot;let&quot; is the lexicographically largest one.
</pre>

Example 2:

<pre>
Input: s = &quot;bb&quot;, k = 2
Output: &quot;b&quot;
Explanation: The longest subsequence repeated 2 times is &quot;b&quot;.
</pre>

Example 3:

<pre>
Input: s = &quot;ab&quot;, k = 2
Output: &quot;&quot;
Explanation: There is no subsequence repeated 2 times. Empty string is returned.
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>n == s.length</code></li>
	<li><code>2 &lt;= n, k &lt;= 2000</code></li>
	<li><code>2 &lt;= n &lt; k * 8</code></li>
	<li><code>s</code> consists of lowercase English letters.</li>
</ul>

longestSubsequenceRepeatedK

Longest Subsequence Repeated k Times

Longest Substring with At Least K Repeating Characters

longest-substring-with-at-least-k-repeating-characters

至少有 K 个重复字符的最长子串

Greedy

String

Backtracking

Counting

Enumeration

给你一个长度为 <code>n</code> 的字符串 <code>s</code> ，和一个整数 <code>k</code> 。请你找出字符串 <code>s</code> 中 重复 <code>k</code> 次的 最长子序列 。

子序列 是由其他字符串删除某些（或不删除）字符派生而来的一个字符串。

如果&nbsp;<code>seq * k</code> 是 <code>s</code> 的一个子序列，其中 <code>seq * k</code> 表示一个由 <code>seq</code> 串联 <code>k</code>&nbsp;次构造的字符串，那么就称 <code>seq</code> 是字符串 <code>s</code> 中一个 重复 <code>k</code> 次 的子序列。

<ul>
	<li>举个例子，<code>"bba"</code> 是字符串 <code>"bababcba"</code> 中的一个重复 <code>2</code> 次的子序列，因为字符串 <code>"bbabba"</code> 是由 <code>"bba"</code> 串联 <code>2</code> 次构造的，而&nbsp;<code>"bbabba"</code> 是字符串 <code>"bababcba"</code> 的一个子序列。</li>
</ul>

返回字符串 <code>s</code> 中 重复 k 次的最长子序列&nbsp; 。如果存在多个满足的子序列，则返回 字典序最大 的那个。如果不存在这样的子序列，返回一个 空 字符串。

&nbsp;

示例 1：

<img alt="example 1" src="https://assets.leetcode.com/uploads/2021/08/30/longest-subsequence-repeat-k-times.png" style="width: 457px; height: 99px;" />

<pre>
输入：s = "letsleetcode", k = 2
输出："let"
解释：存在两个最长子序列重复 2 次：let" 和 "ete" 。
"let" 是其中字典序最大的一个。
</pre>

示例 2：

<pre>
输入：s = "bb", k = 2
输出："b"
解释：重复 2 次的最长子序列是 "b" 。
</pre>

示例 3：

<pre>
输入：s = "ab", k = 2
输出：""
解释：不存在重复 2 次的最长子序列。返回空字符串。
</pre>

&nbsp;

提示：

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