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>
Producción:
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