算法（如何计算每个字符至少出现k次的最长子序列（）） _字符串

本文概述

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

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

Input : str = "lsbin"k = 2Output : geeksgeeksEvery character in the outputsubsequence appears at-least 2times.Input : str = "aabbaabacabb"k = 5Output : aabbaabaabb

推荐：请尝试以下方法{IDE}首先, 在继续解决方案之前。方法1(强力)
We
生成所有子序列
。对于每个子序列, 请计算其中的不同字符, 并找出每个字符至少出现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 timesclass 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 timesMAX_CHARS = 26def 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# 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

输出如下：