Largest index for each distinct character in given string with frequency K
Given a string S consisting of lowercase English letters and an integer K, the task is to find, for each distinct character in S, the largest index having this character exactly K times. If no such characters exist, print -1. Print the result in a lexicographical ordering.
Note: Consider 0-based indexing in S.
Examples:
Input: S = “cbaabaacbcd”, K = 2
Output: { {a 4}, {b 7}, {c 8} }
Explanation:
For ‘a’, the largest index having 2 a’s is “cbaab”.
For ‘b’, the largest index having 2 b’s is “cbaabaac”.
For ‘c’, the largest index having 2 c’s is “cbaabaacb”.
For ‘d’, the is no index up to which we have 2 d’sInput: P = “acbacbacbaba”, K = 3
Output: { {a 8}, {b 9}, {c 11} }
Approach: The idea is to first find all the distinct characters in string S. Then for each lowercase English character, check whether it is present in S or not and run a for loop from the beginning of S and maintain the count of that character that occurred till now. When the count becomes equal to K update the index answer accordingly. Finally, append this character and its corresponding index in the vector result.
Below is the implementation of the above approach.
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // Function to find largest index for each // distinct character occurring 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 occurring 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 occurring 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 occurring 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 |
Javascript
<script> // JavaScript implementation of the approach // Function to find largest // index for each distinct // character occurring exactly K times. function maxSubString(S, K, N) { // Finding all characters present in S var freq = new Array(26).fill(0); // Finding all distinct characters in S for ( var i = 0; i < N; ++i) { freq[S[i].charCodeAt(0) - "a" .charCodeAt(0)] = 1; } // To store result for each character var answer = []; // Loop through each lower case // English character for ( var i = 0; i < 26; ++i) { // If current character is absent in s if (freq[i] === 0) continue ; // Getting current character var ch = String.fromCharCode(i + 97); // Finding count of character ch in S var count = 0; // To store max Index encountred so far var index = -1; for ( var j = 0; j < N; ++j) { if (S[j] === ch) count++; if (count === K) index = j; } answer.push([ch, index]); } var flag = 0; // Printing required result for ( var i = 0; i < answer.length; ++i) { if (answer[i][1] > -1) { flag = 1; document.write(answer[i][0] + " " + answer[i][1] + "<br>" ); } } // If no such character exists, print -1 if (flag === 0) document.write( "-1" + "<br>" ); } // Driver code var S = "cbaabaacbcd" ; var K = 2; var N = S.length; maxSubString(S.split( "" ), K, N); </script> |
a 4 b 7 c 8
Time Complexity: O(26 * N)
Auxiliary Space: O(1)