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

给定一个字符串“s”和一个整数k，找到另一个字符串“t”，使“t”是给定字符串“s”的最大子序列，“t”的每个字符在字符串s中必须至少出现k次。 例如：

null

Input : s = "geeksforgeeks"        k = 2Output : geeksgeeksInput : s = "baaabaacba"        k = 3Output : baaabaaba

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

A. 简单解决方案 就是生成所有子序列 .对于每个子序列，检查其是否至少包含k次所有字符。找到这样的子序列。这种方法的时间复杂度是指数的。 有效的方法 我们可以使用另一个数组来保存字符串s中每个字符的计数记录，如果任何字符出现的次数超过或等于k次，那么我们只需打印它。

CPP

                         // CPP Program to find the subsequence                       
                         // with each character occurring at least                       
                         // k times in string s                       
                         #include <iostream>                       
                         using                                     namespace                                     std;                       
           
                         #define MAX_CHAR 26                       
           
                         // Function to find the subsequence                       
                         void                                     findSubsequence(string str,                                     int                                     k)                       
                         {                       
                                                 // Taking an extra array to keep                       
                                                 // record for character count in s                       
                                                 int                                     a[MAX_CHAR] = { 0 };                       
           
                                                 // Counting occurrences of all                       
                                                 // characters in str[]                       
                                                 for                                     (                                     int                                     i = 0; i < str.size(); i++)                       
                                                 a[str[i] -                                     'a'                                     ]++;                       
           
                                                 // Printing characters with count                       
                                                 // >= k in same order as they appear                       
                                                 // in str.                       
                                                 for                                     (                                     int                                     i = 0; i < l; i++)                       
                                                 if                                     (a[str[i] -                                     'a'                                     ] >= k)                       
                                                 cout << str[i];                       
                         }                       
           
                         // Driver code                       
                         int                                     main()                       
                         {                       
                                                 int                                     k = 2;                       
                                                 findSubsequence(                                     "geeksforgeeks"                                     , k);                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java Program to find the subsequence                       
                         // with each character occurring at least                       
                         // k times in string s                       
                         class                                     GFG {                       
                                   
                                                 static                                     final                                     int                                     MAX_CHAR =                                     26                                     ;                       
                                   
                                                 // Function to find the subsequence                       
                                                 static                                     void                                     findSubsequence(String str,                                     int                                     k)                       
                                                 {                       
                                   
                                                 // Taking an extra array to keep                       
                                                 // record for character count in s                       
                                                 int                                     a[] =                                     new                                     int                                     [MAX_CHAR];                       
                                   
                                                 // Counting occurrences of all                       
                                                 // characters in str[]                       
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < str.length(); i++)                       
                                                 a[str.charAt(i) -                                     'a'                                     ]++;                       
                                   
                                                 // Printing characters with count                       
                                                 // >= k in same order as they appear                       
                                                 // in str.                       
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < str.length(); i++)                       
                                                 if                                     (a[str.charAt(i) -                                     'a'                                     ] >= k)                       
                                                 System.out.print(str.charAt(i));                       
                                                 }                       
                                   
                                                 // Driver code                       
                                                 public                                     static                                     void                                     main(String[] args) {                       
                                   
                                                 int                                     k =                                     2                                     ;                       
                                                 findSubsequence(                                     "geeksforgeeks"                                     , k);                       
                                                 }                       
                         }                       
           
                         // This code is contributed by Anant Agarwal.                       

Python3

                         # Python Program to find the subsequence                       
                         # with each character occurring at least                       
                         # k times in string s                       
           
                         MAX_CHAR                                     =                                     26                       
           
                         # Function to find the subsequence                       
                         def                                     findSubsequence(stri, k):                       
                                                 # Taking an extra array to keep                       
                                                 # record for character count in s                       
                                                 a                                     =                                     [                                     0                                     ]                                     *                                     MAX_CHAR;                       
           
                                                 # Counting occurrences of all                       
                                                 # characters in str[]                       
                                                 for                                     i                                     in                                     range                                     (                                     len                                     (stri)):                       
                                                 a[                                     ord                                     (stri[i])                                     -                                     ord                                     (                                     'a'                                     )]                                     +                                     =                                     1                       
           
                                                 # Printing characters with count                       
                                                 # >= k in same order as they appear                       
                                                 # in str.                       
                                                 for                                     i                                     in                                     range                                     (                                     len                                     (stri)):                       
                                                 if                                     a[                                     ord                                     (stri[i])                                     -                                     ord                                     (                                     'a'                                     )] >                                     =                                     k:                       
                                                 print                                     (stri[i],end                                     =                                     '')                       
           
                         # Driver code                       
                         k                                     =                                     2                       
                         findSubsequence(                                     "geeksforgeeks"                                     , k)                       
           
                         # This code is contributed by Shubham Rana                       

C#

                         // C# Program to find the subsequence                       
                         // with each character occurring at                       
                         // least k times in string s                       
                         using                                     System;                       
           
                         class                                     GFG {                       
                                   
                                                 static                                     int                                     MAX_CHAR = 26;                       
                                   
                                                 // Function to find the subsequence                       
                                                 static                                     void                                     findSubsequence(                                     string                                     str,                                     int                                     k)                       
                                                 {                       
                                   
                                                 // Taking an extra array to keep                       
                                                 // record for character count in s                       
                                                 int                                     []a =                                     new                                     int                                     [MAX_CHAR];                       
                                   
                                                 // Counting occurrences of all                       
                                                 // characters in str[]                       
                                                 for                                     (                                     int                                     i = 0; i < str.Length; i++)                       
                                                 a[str[i] -                                     'a'                                     ]++;                       
                                   
                                                 // Printing characters with count                       
                                                 // >= k in same order as they appear                       
                                                 // in str.                       
                                                 for                                     (                                     int                                     i = 0; i < str.Length; i++)                       
                                                 if                                     (a[str[i] -                                     'a'                                     ] >= k)                       
                                                 Console.Write(str[i]);                       
                                                 }                       
                                   
                                                 // Driver code                       
                                                 public                                     static                                     void                                     Main() {                       
                                   
                                                 int                                     k = 2;                       
                                                 findSubsequence(                                     "geeksforgeeks"                                     , k);                       
                                                 }                       
                         }                       
           
                         // This code is contributed by vt_m.                       

PHP

                         <?php                       
                         // PHP Program to find the                       
                         // subsequence with each                       
                         // character occurring at                       
                         // least k times in string s                       
           
                         // Function to find the subsequence                       
                         function                                     findSubsequence(                                     $str                                     ,                                     $k                                     )                       
                         {                       
                                   
                                                 // Taking an extra array to keep                       
                                                 // record for character count in s                       
                                                 $a                                     =                                     array                                     (1024);                       
                                   
                                                 for                                     (                                     $i                                     = 0;                                     $i                                     < 26;                                     $i                                     ++)                       
                                                 $a                                     [                                     $i                                     ] = 0;                       
                                   
                                                 // Counting occurrences of all                       
                                                 // characters in str[]                       
                                                 for                                     (                                     $i                                     = 0;                                     $i                                     <                                     strlen                                     (                                     $str                                     );                                     $i                                     ++)                       
                                                 {                       
                                                 $temp                                     = ord(                                     $str                                     [                                     $i                                     ]) - ord(                                     'a'                                     );                       
                                                 $a                                     [                                     $temp                                     ] += 1;                       
                                                 }                       
                                   
                                                 // Printing characters with                       
                                                 // count >= k in same order                       
                                                 // as they appear in str.                       
                                                 for                                     (                                     $i                                     = 0;                                     $i                                     <                                     strlen                                     (                                     $str                                     );                                     $i                                     ++)                       
                                                 if                                     (                                     $a                                     [ord(                                     $str                                     [                                     $i                                     ]) - ord(                                     'a'                                     )] >=                                     $k                                     )                       
                                                 echo                                     $str                                     [                                     $i                                     ];                       
                         }                       
           
                         // Driver code                       
                         $k                                     = 2;                       
                         findSubsequence(                                     "geeksforgeeks"                                     ,                                     $k                                     );                       
                                   
                         // This code is contributed by Sam007                       
                         ?>                       

Javascript

                         <script>                       
           
                         // Javascript Program to find the subsequence                       
                         // with each character occurring at least                       
                         // k times in string s                       
           
                         var                                     MAX_CHAR = 26;                       
           
                         // Function to find the subsequence                       
                         function                                     findSubsequence(str, k)                       
                         {                       
                                                 // Taking an extra array to keep                       
                                                 // record for character count in s                       
                                                 var                                     a = Array(MAX_CHAR).fill(0);                       
           
                                                 // Counting occurrences of all                       
                                                 // characters in str[]                       
                                                 for                                     (                                     var                                     i = 0; i < str.length; i++)                       
                                                 a[str[i].charCodeAt(0) -                       
                                                 'a'                                     .charCodeAt(0)]++;                       
           
                                                 // Printing characters with count                       
                                                 // >= k in same order as they appear                       
                                                 // in str.                       
                                                 for                                     (                                     var                                     i = 0; i < str.length; i++)                       
                                                 if                                     (a[str[i].charCodeAt(0) -                       
                                                 'a'                                     .charCodeAt(0)] >= k)                       
                                                 document.write( str[i]);                       
                         }                       
           
                         // Driver code                       
                         var                                     k = 2;                       
                         findSubsequence(                                     "geeksforgeeks"                                     , k);                       
           
                         </script>                       

输出：

geeksgeeks

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

THE END

技术文章