给定字符串中频率为K的每个不同字符的最大索引

本文概述

C ++
Java
Python3
C#

给定一个由英文小写字母和整数K组成的字符串S，任务是找到S中每个不同字符的最大索引恰好K次。如果不存在这样的字符，则打印-1。按字典顺序打印结果。
注意：考虑S中基于0的索引。
【给定字符串中频率为K的每个不同字符的最大索引】例子：

输入：S ="cbaabaacbcd", K = 2
输出：{{a 4}, {b 7}, {c 8}}
说明：
对于"a", 具有2 a的最大索引是"cbaab"。
对于"b", 具有2个b的最大索引是"cbaabaac"。
对于"c", 具有2个c的最大索引是"cbaabaacb"。
对于"d", 没有索引, 我们有2 d个
输入：P ="acbacbacbaba", K = 3
输出：{{a 8}, {b 9}, {c 11}}

方法：这个想法是首先找到字符串S中的所有不同字符。然后, 对于每个小写英文字符, 检查它是否存在于S中, 并从S的开头运行一个for循环, 并保持该字符的计数到现在为止。当计数等于K时, 相应地更新索引答案。最后, 将此字符及其对应的索引附加到向量结果中。
下面是上述方法的实现。
C ++

//C++ implementation of the approach#include < bits/stdc++.h> using namespace std; //Function to find largest index for each //distinct character occuring exactly K times. void maxSubstring(string& S, int K, int N) {//finding all characters present in S int freq[26]; memset (freq, 0, sizeof freq); //Finding all distinct characters in S for ( int i = 0; i < N; ++i) { freq[S[i] - 'a' ] = 1; }//vector to store result for each character vector< pair< char , int> > answer; //loop through each lower case English character for ( int i = 0; i < 26; ++i) {//if current character is absent in s if (freq[i] == 0) continue ; //getting current character char ch = i + 97; //finding count of character ch in S int count = 0; //to store max Index encountred so far int index = -1; for ( int j = 0; j < N; ++j) { if (S[j] == ch) count++; if (count == K) index = j; }answer.push_back({ ch, index }); }int flag = 0; //printing required result for ( int i = 0; i < ( int )answer.size(); ++i) {if (answer[i].second> -1) { flag = 1; cout < < answer[i].first < < " " < < answer[i].second < < endl; } }//If no such character exists, print -1 if (flag == 0) cout < < "-1" < < endl; }//Driver code int main() { string S = "cbaabaacbcd" ; int K = 2; int N = S.length(); maxSubstring(S, K, N); return 0; }

Java

//Java implementation of the approach import java.util.*; class GFG{ static class pair {char first; intsecond; public pair( char first, int second) { this .first = first; this .second = second; } } //Function to find largest //index for each distinct //character occuring exactly K times. static void maxSubString( char [] S, int K, int N) { //finding all characters present in S int []freq = new int [ 26 ]; //Finding all distinct characters in S for ( int i = 0 ; i < N; ++i) { freq[S[i] - 'a' ] = 1 ; }//vector to store result for each character Vector< pair> answer = new Vector< pair> (); //loop through each lower case English character for ( int i = 0 ; i < 26 ; ++i) { //if current character is absent in s if (freq[i] == 0 ) continue ; //getting current character char ch = ( char ) (i + 97 ); //finding count of character ch in S int count = 0 ; //to store max Index encountred so far int index = - 1 ; for ( int j = 0 ; j < N; ++j) { if (S[j] == ch) count++; if (count == K) index = j; } answer.add( new pair(ch, index )); }int flag = 0 ; //printing required result for ( int i = 0 ; i < ( int )answer.size(); ++i) { if (answer.get(i).second> - 1 ) { flag = 1 ; System.out.print(answer.get(i).first + " " + answer.get(i).second + "\n" ); } }//If no such character exists, print -1 if (flag == 0 ) System.out.print( "-1" + "\n" ); }//Driver code public static void main(String[] args) { String S = "cbaabaacbcd" ; int K = 2 ; int N = S.length(); maxSubString(S.toCharArray(), K, N); } }//This code is contributed by shikhasingrajput

Python3

# Python3 implementation of the approach # Function to find largest index for each # distinct character occuring exactly K times. def maxSubstring(S, K, N):# Finding all characters present in S freq = [ 0 for i in range ( 26 )]# Finding all distinct characters in S for i in range (N): freq[ ord (S[i]) - 97 ] = 1# To store result for each character answer = []# Loop through each lower # case English character for i in range ( 26 ):# If current character is absent in s if (freq[i] = = 0 ): continue# Getting current character ch = chr (i + 97 )# Finding count of character ch in S count = 0# To store max Index encountred so far index = - 1for j in range (N): if (S[j] = = ch): count + = 1if (count = = K): index = janswer.append([ch, index])flag = 0# Printing required result for i in range ( len (answer)): if (answer[i][ 1 ]> - 1 ): flag = 1 print (answer[i][ 0 ], answer[i][ 1 ])# If no such character exists, # print -1 if (flag = = 0 ): print ( "-1" )# Driver code if __name__ = = '__main__' :S = "cbaabaacbcd" K = 2 N = len (S)maxSubstring(S, K, N)# This code is contributed by Surendra_Gangwar

//C# implementation of the approach using System; using System.Collections.Generic; class GFG{class pair { public char first; public int second; public pair( char first, int second) { this .first = first; this .second = second; } } //Function to find largest //index for each distinct //character occuring exactly K times. static void maxSubString( char [] S, int K, int N) {//Finding all characters present in S int []freq = new int [26]; //Finding all distinct characters in S for ( int i = 0; i < N; ++i) { freq[S[i] - 'a' ] = 1; }//To store result for each character List< pair> answer = new List< pair> (); //Loop through each lower case //English character for ( int i = 0; i < 26; ++i) {//If current character is absent in s if (freq[i] == 0) continue ; //Getting current character char ch = ( char )(i + 97); //Finding count of character ch in S int count = 0; //To store max Index encountred so far int index = -1; for ( int j = 0; j < N; ++j) { if (S[j] == ch) count++; if (count == K) index = j; } answer.Add( new pair(ch, index)); }int flag = 0; //Printing required result for ( int i = 0; i < ( int )answer.Count; ++i) { if (answer[i].second> -1) { flag = 1; Console.Write(answer[i].first + " " + answer[i].second + "\n" ); } }//If no such character exists, print -1 if (flag == 0) Console.Write( "-1" + "\n" ); }//Driver code public static void Main(String[] args) { String S = "cbaabaacbcd" ; int K = 2; int N = S.Length; maxSubString(S.ToCharArray(), K, N); } }//This code is contributed by Amit Katiyar

输出如下：