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

2021年4月28日19:40:55 发表评论 846 次浏览

本文概述

给定一个由英文小写字母和整数K组成的字符串S，任务是找到S中每个不同字符的最大索引恰好K次。如果不存在这样的字符，则打印-1。按字典顺序打印结果。

注意：考虑S中基于0的索引。

例子：

输入：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;
         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 ;
     }
  
     //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 = - 1
  
         for j in range (N):
             if (S[j] = = ch):
                 count + = 1
  
             if (count = = K):
                 index = j
  
         answer.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#

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

输出如下：

a 4
b 7
c 8

时间复杂度：O(26 * N)

木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: