Dada una string S que consta de letras inglesas en minúsculas y un número entero K , la tarea es encontrar, para cada carácter distinto en S, el índice más grande que tenga este carácter exactamente K veces. Si no existen tales caracteres, imprima -1. Imprime el resultado en un ordenamiento lexicográfico.
Nota: considere la indexación basada en 0 en S.
Ejemplos:
Entrada: S = “cbaabaacbcd”, K = 2
Salida: { {a 4}, {b 7}, {c 8} }
Explicación:
Para ‘a’, el índice más grande que tiene 2 a es “cbaab”.
Para ‘b’, el índice más grande que tiene 2 b es “cbaabaac”.
Para ‘c’, el índice más grande que tiene 2 c es “cbaabaacb”.
Para ‘d’, no hay índice hasta el cual tengamos 2 dEntrada: P = “acbacbacbaba”, K = 3
Salida: { {a 8}, {b 9}, {c 11} }
Enfoque: la idea es encontrar primero todos los caracteres distintos en la string S . Luego, para cada carácter en minúsculas en inglés, verifique si está presente en S o no y ejecute un ciclo for desde el comienzo de S y mantenga la cuenta de ese carácter ocurrido hasta ahora. Cuando el recuento sea igual a K, actualice la respuesta del índice en consecuencia. Finalmente, agregue este carácter y su índice correspondiente en el resultado del vector.
A continuación se muestra la implementación del enfoque anterior.
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
Complejidad de tiempo: O(26 * N)
Publicación traducida automáticamente
Artículo escrito por Sanjit_Prasad y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA