Índice más grande para cada carácter distinto en una string dada con frecuencia K

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 d

Entrada: 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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *