算法：如何计算每个字符至少出现k次的最长子序列？

2021年3月19日18:21:40 发表评论 768 次浏览

本文概述

建议：在继续解决方案之前, 请先在{IDE}上尝试使用你的方法。
C ++
Java
Python 3
C#

给定一个字符串和一个数字k, 找出最长的子序列每个字符至少出现k次的字符串。

例子：

Input : str = "lsbin"
         k = 2
Output : geeksgeeks
Every character in the output
subsequence appears at-least 2
times.

Input : str = "aabbaabacabb"
          k = 5
Output : aabbaabaabb

推荐：请尝试以下方法{IDE}首先, 在继续解决方案之前。

方法1(强力)

生成所有子序列

。对于每个子序列, 请计算其中的不同字符, 并找出每个字符至少出现k次的最长子序列。

方法2(有效方式)

1.查找字符串的频率, 并将其存储在大小为26的整数数组中, 该整数表示字母。

2.找到频率后, 逐个字符地迭代字符串, 如果该字符的频率大于或等于所需的重复次数, 则仅在此位置打印该字符。

C ++

// C++ program to Find longest subsequence where
//  every character appears at-least k times
#include<bits/stdc++.h>
using namespace std;
  
const int MAX_CHARS = 26;
  
void longestSubseqWithK(string str, int k)    
{
     int n = str.size();                   
  
     // Count frequencies of all characters
     int freq[MAX_CHARS] = {0};                    
     for ( int i = 0 ; i < n; i++)    
         freq[str[i] - 'a' ]++;              
      
     // Traverse given string again and print
     // all those characters whose frequency
     // is more than or equal to k.
     for ( int i = 0 ; i < n ; i++)   
         if (freq[str[i] - 'a' ] >= k)               
             cout << str[i];      
}
  
// Driver code
int main() {
     string str = "lsbin" ;
     int k = 2;
     longestSubseqWithK(str, k);       
     return 0;
}

Java

// Java program to Find longest subsequence where
//  every character appears at-least k times
  
class GFG {
  
     static final int MAX_CHARS = 26 ;
  
     static void longestSubseqWithK(String str, int k) {
         int n = str.length();
  
         // Count frequencies of all characters
         int freq[] = new int [MAX_CHARS];
         for ( int i = 0 ; i < n; i++) {
             freq[str.charAt(i) - 'a' ]++;
         }
  
         // Traverse given string again and print
         // all those characters whose frequency
         // is more than or equal to k.
         for ( int i = 0 ; i < n; i++) {
             if (freq[str.charAt(i) - 'a' ] >= k) {
                 System.out.print(str.charAt(i));
             }
         }
     }
  
// Driver code
     static public void main(String[] args) {
         String str = "lsbin" ;
         int k = 2 ;
         longestSubseqWithK(str, k);
  
     }
}
  
// This code is contributed by Rajput-Ji

Python 3

# Python 3 program to Find longest subsequence where
#  every character appears at-least k times
   
MAX_CHARS = 26
   
def longestSubseqWithK( str , k):    
  
     n = len ( str )                  
   
     # Count frequencies of all characters
     freq = [ 0 ] * MAX_CHARS                 
     for i in range (n):  
         freq[ ord ( str [i]) - ord ( 'a' )] + = 1              
       
     # Traverse given string again and print
     # all those characters whose frequency
     # is more than or equal to k.
     for i in range (n ):
         if (freq[ ord ( str [i]) - ord ( 'a' )] > = k):               
             print ( str [i], end = "")
   
# Driver code
if __name__ = = "__main__" :
      
     str = "lsbin"
     k = 2
     longestSubseqWithK( str , k)

C#

// C# program to Find longest subsequence where
//  every character appears at-least k times
using System; 
public class GFG {
   
     static readonly int MAX_CHARS = 26;
   
     static void longestSubseqWithK(String str, int k) {
         int n = str.Length;
   
         // Count frequencies of all characters
         int []freq = new int [MAX_CHARS];
         for ( int i = 0; i < n; i++) {
             freq[str[i]- 'a' ]++;
         }
   
         // Traverse given string again and print
         // all those characters whose frequency
         // is more than or equal to k.
         for ( int i = 0; i < n; i++) {
             if (freq[str[i] - 'a' ] >= k) {
                 Console.Write(str[i]);
             }
         }
     }
   
// Driver code
     static public void Main() {
         String str = "lsbin" ;
         int k = 2;
         longestSubseqWithK(str, k);
   
     }
}
   
// This code is contributed by Rajput-Ji

输出如下：