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

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

## 本文概述

``````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}首先, 在继续解决方案之前。

We

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

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``````

``geeksgeeks``