字典中最大的子序列，每个字符至少出现k次-yiteyi-C++库

给一根绳子 s 还有一个整数 K .任务是找到S的最大子序列，比如T，这样T中的每个字符都必须至少出现K次。 例如：

null

Input : S = "banana", K = 2.
Output : nn
Possible subsequence where each character exists at least 2 times are:

Check if a line touches or intersects a circle

From the above subsequences, "nn" is the lexicographically largest.

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

这个想法是为了贪婪地解决上述问题。如果我们想让子序列在字典上最大，我们必须优先考虑在字典上更大的字符。”z’是最大的字符，假设z出现在f中 _Z S.If.f时代 _Z >=K，在字符串T中添加’z’z K次，并继续从S的左侧删除字符，直到删除所有z。用“y”、“w”、“….”来应用策略a’。最后，你会找到答案。让我们来看一个例子。假设S=“zzwzawa”和K=2。以最大的字符“z”开头。这里是f _Z 因此T将变成“zzz”，我们将删除S左边的字母，直到所有z都被删除。所以现在S将变成“awa”。下一个最大值是“y”，但它在k中出现0次，所以我们将跳过它。我们也会跳过“w”、“v”等，直到出现两次“a”。现在T将变成“zzzaa”，S将变成一个空字符串。我们的答案是“zzzaa”。以下是该方法的实施：

C++

                         // C++ program to find lexicographically largest                       
                         // subsequence where every character appears at                       
                         // least k times.                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
                                   
                         // Find lexicographically largest subsequence of                       
                         // s[0..n-1] such that every character appears                       
                         // at least k times. The result is filled in t[]                       
                         void                                     subsequence(                                     char                                     s[],                                     char                                     t[],                                     int                                     n,                                     int                                     k)                       
                         {                       
                                                 int                                     last = 0, cnt = 0, new_last = 0, size = 0;                       
                                   
                                                 // Starting from largest charter 'z' to 'a'                       
                                                 for                                     (                                     char                                     ch =                                     'z'                                     ; ch >=                                     'a'                                     ; ch--) {                       
                                                 cnt = 0;                       
                                   
                                                 // Counting the frequency of the character                       
                                                 for                                     (                                     int                                     i = last; i < n; i++) {                       
                                                 if                                     (s[i] == ch)                       
                                                 cnt++;                       
                                                 }                       
                                   
                                                 // If frequency is greater than k                       
                                                 if                                     (cnt >= k) {                       
                                   
                                                 // From the last point we leave                       
                                                 for                                     (                                     int                                     i = last; i < n; i++) {                       
                                   
                                                 // check if string contain ch                       
                                                 if                                     (s[i] == ch) {                       
                                   
                                                 // If yes, append to output string                       
                                                 t[size++] = ch;                       
                                                 new_last = i;                       
                                                 }                       
                                                 }                       
                                   
                                                 // Update the last point.                       
                                                 last = new_last;                       
                                                 }                       
                                                 }                       
                                                 t[size] =                                     ' '                                     ;                       
                         }                       
                                   
                         // Driver code                       
                         int                                     main()                       
                         {                       
                                                 char                                     s[] =                                     "banana"                                     ;                       
                                                 int                                     n =                                     sizeof                                     (s);                       
                                                 int                                     k = 2;                       
                                                 char                                     t[n];                       
                                                 subsequence(s, t, n - 1, k);                       
                                                 cout << t << endl;                       
                                                 return                                     0;                       
                         }                       

JAVA

                         import                                     java.util.Arrays;                       
                                   
                                   
                         // Java program to find lexicographically largest                       
                         // subsequence where every character appears at                       
                         // least k times.                       
                         class                                     GFG {                       
                                   
                         // Find lexicographically largest subsequence of                       
                         // s[0..n-1] such that every character appears                       
                         // at least k times. The result is filled in t[]                       
                         static                                     void                                     subsequence(                                     char                                     s[],                                     char                                     t[],                                     int                                     n,                                     int                                     k)                       
                         {                       
                                                 int                                     last =                                     0                                     , cnt =                                     0                                     , new_last =                                     0                                     , size =                                     0                                     ;                       
                                   
                                                 // Starting from largest charter 'z' to 'a'                       
                                                 for                                     (                                     char                                     ch =                                     'z'                                     ; ch >=                                     'a'                                     ; ch--) {                       
                                                 cnt =                                     0                                     ;                       
                                   
                                                 // Counting the frequency of the character                       
                                                 for                                     (                                     int                                     i = last; i < n; i++) {                       
                                                 if                                     (s[i] == ch)                       
                                                 cnt++;                       
                                                 }                       
                                   
                                                 // If frequency is greater than k                       
                                                 if                                     (cnt >= k) {                       
                                   
                                                 // From the last point we leave                       
                                                 for                                     (                                     int                                     i = last; i < n; i++) {                       
                                   
                                                 // check if string contain ch                       
                                                 if                                     (s[i] == ch) {                       
                                   
                                                 // If yes, append to output string                       
                                                 t[size++] = ch;                       
                                                 new_last = i;                       
                                                 }                       
                                                 }                       
                                   
                                                 // Update the last point.                       
                                                 last = new_last;                       
                                                 }                       
                                                 }                       
                                                 t[size] =                                     ' '                                     ;                       
                         }                       
                                   
                         // Driver code                       
                                                 public                                     static                                     void                                     main(String[] args) {                       
                                                 char                                     s[] = {                                     'b'                                     ,                                     'a'                                     ,                                     'n'                                     ,                                     'a'                                     ,                                     'n'                                     ,                                     'a'                                     };                       
                                                 int                                     n = s.length;                       
                                                 int                                     k =                                     2                                     ;                       
                                                 char                                     t[] =                                     new                                     char                                     [n];                       
                                                 subsequence(s, t, n -                                     1                                     , k);                       
                                                 for                                     (                                     int                                     i =                                     0                                     ;i<t.length;i++)                       
                                                 if                                     (t[i]!=                                     0                                     )                       
                                                 System.out.print(t[i]);                       
                                   
                                                 }                       
                         }                       
                                   
                         // This code is contributed by Jajput-Ji                       

Python3

                         # Python3 program to find lexicographically largest                       
                         # subsequence where every character appears at                       
                         # least k times.                       
                                   
                         # Find lexicographically largest subsequence of                       
                         # s[0..n-1] such that every character appears                       
                         # at least k times. The result is filled in t[]                       
                         def                                     subsequence(s, t, n, k):                       
                                                 last                                     =                                     0                       
                                                 cnt                                     =                                     0                       
                                                 new_last                                     =                                     0                       
                                                 size                                     =                                     0                       
                                   
                                                 string                                     =                                     'zyxwvutsrqponmlkjihgfedcba'                       
                                   
                                                 # Starting from largest charter 'z' to 'a'                       
                                                 for                                     ch                                     in                                     string:                       
                                                 cnt                                     =                                     0                       
                                                 for                                     i                                     in                                     range                                     (last, n):                       
                                                 if                                     s[i]                                     =                                     =                                     ch:                       
                                                 cnt                                     +                                     =                                     1                       
                                   
                                                 # If frequency is greater than k                       
                                                 if                                     cnt >                                     =                                     k:                       
                                   
                                                 # From the last point we leave                       
                                                 for                                     i                                     in                                     range                                     (last, n):                       
                                   
                                                 # check if string contain ch                       
                                                 if                                     s[i]                                     =                                     =                                     ch:                       
                                   
                                                 # If yes, append to output string                       
                                                 t[size]                                     =                                     ch                       
                                                 new_last                                     =                                     i                       
                                                 size                                     +                                     =                                     1                       
                                   
                                                 # Update the last point.                       
                                                 last                                     =                                     new_last                       
                                   
                         # Driver Code                       
                         if                                     __name__                                     =                                     =                                     "__main__"                                     :                       
                                                 s                                     =                                     [                                     'b'                                     ,                                     'a'                                     ,                                     'n'                                     ,                                     'a'                                     ,                                     'n'                                     ,                                     'a'                                     ]                       
                                                 n                                     =                                     len                                     (s)                       
                                                 k                                     =                                     2                       
                                                 t                                     =                                     ['']                                     *                                     n                       
                                                 subsequence(s, t, n                                     -                                     1                                     , k)                       
                                                 t                                     =                                     ''.join(t)                       
                                                 print                                     (t)                       
                                   
                         # This code is contributed by                       
                         # sanjeev2552                       

C#

                         // C# program to find lexicographically                       
                         // largest subsequence where every                       
                         // character appears at least k times.                       
                         using                                     System;                       
                                   
                         class                                     GFG                       
                         {                       
                                   
                         // Find lexicographically largest subsequence                       
                         // of s[0..n-1] such that every character                       
                         // appears at least k times. The result is                       
                         // filled in t[]                       
                         static                                     void                                     subsequence(                                     char                                     []s,                                     char                                     []t,                       
                                                 int                                     n,                                     int                                     k)                       
                         {                       
                                                 int                                     last = 0, cnt = 0,                       
                                                 new_last = 0, size = 0;                       
                                   
                                                 // Starting from largest character                       
                                                 // 'z' to 'a'                       
                                                 for                                     (                                     char                                     ch =                                     'z'                                     ; ch >=                                     'a'                                     ; ch--)                       
                                                 {                       
                                                 cnt = 0;                       
                                   
                                                 // Counting the frequency of                       
                                                 // the character                       
                                                 for                                     (                                     int                                     i = last; i < n; i++)                       
                                                 {                       
                                                 if                                     (s[i] == ch)                       
                                                 cnt++;                       
                                                 }                       
                                   
                                                 // If frequency is greater than k                       
                                                 if                                     (cnt >= k)                       
                                                 {                       
                                   
                                                 // From the last point we leave                       
                                                 for                                     (                                     int                                     i = last; i < n; i++)                       
                                                 {                       
                                   
                                                 // check if string contain ch                       
                                                 if                                     (s[i] == ch)                       
                                                 {                       
                                   
                                                 // If yes, append to output string                       
                                                 t[size++] = ch;                       
                                                 new_last = i;                       
                                                 }                       
                                                 }                       
                                   
                                                 // Update the last point.                       
                                                 last = new_last;                       
                                                 }                       
                                                 }                       
                                                 t[size] =                                     ' '                                     ;                       
                         }                       
                                   
                         // Driver code                       
                         public                                     static                                     void                                     Main()                       
                         {                       
                                                 char                                     []s = {                                     'b'                                     ,                                     'a'                                     ,                                     'n'                                     ,                                     'a'                                     ,                                     'n'                                     ,                                     'a'                                     };                       
                                                 int                                     n = s.Length;                       
                                                 int                                     k = 2;                       
                                                 char                                     []t =                                     new                                     char                                     [n];                       
                                                 subsequence(s, t, n - 1, k);                       
                                                 for                                     (                                     int                                     i = 0; i < t.Length; i++)                       
                                                 if                                     (t[i] != 0)                       
                                                 Console.Write(t[i]);                       
                         }                       
                         }                       
                                   
                         // This code contributed by Rajput-Ji                       

Javascript

                         <script>                       
                                   
                                   
                         // Javascript program to find                       
                         // lexicographically largest                       
                         // subsequence where every                       
                         // character appears at                       
                         // least k times.                       
                                   
                         // Find lexicographically largest subsequence of                       
                         // s[0..n-1] such that every character appears                       
                         // at least k times. The result is filled in t[]                       
                         function                                     subsequence(s, t, n, k)                       
                         {                       
                                                 var                                     last = 0, cnt = 0, new_last = 0, size = 0;                       
                                   
                                                 // Starting from largest charter 'z' to 'a'                       
                                                 for                                     (                                     var                                     ch =                                     'z'                                     .charCodeAt(0);                       
                                                 ch >=                                     'a'                                     .charCodeAt(0); ch--)                       
                                                 {                       
                                                 cnt = 0;                       
                                   
                                                 // Counting the frequency of the character                       
                                                 for                                     (                                     var                                     i = last; i < n; i++) {                       
                                                 if                                     (s[i].charCodeAt(0) == ch)                       
                                                 cnt++;                       
                                                 }                       
                                   
                                                 // If frequency is greater than k                       
                                                 if                                     (cnt >= k) {                       
                                   
                                                 // From the last point we leave                       
                                                 for                                     (                                     var                                     i = last; i < n; i++) {                       
                                   
                                                 // check if string contain ch                       
                                                 if                                     (s[i].charCodeAt(0) == ch) {                       
                                   
                                                 // If yes, append to output string                       
                                                 t[size++] = String.fromCharCode(ch);                       
                                                 new_last = i;                       
                                                 }                       
                                                 }                       
                                   
                                                 // Update the last point.                       
                                                 last = new_last;                       
                                                 }                       
                                                 }                       
                         }                       
                                   
                         // Driver code                       
                         var                                     s =                                     "banana"                                     ;                       
                         var                                     n = s.length;                       
                         var                                     k = 2;                       
                         var                                     t = Array(n);                       
                         subsequence(s, t, n - 1, k);                       
                         document.write( t.join(                                     ''                                     ) );                       
                                   
                                   
                         </script>                       

输出：

nn

本文由 Anuj Chauhan（anuj0503） .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章