Encuentra el número de ocurrencias de un carácter hasta la posición anterior

Dada una string S de longitud N y un número entero P (1≤P≤N) que denota la posición de un carácter en la string. La tarea es encontrar el número de ocurrencias del carácter presente en la posición P hasta el índice P-1.

Ejemplos: 

Entrada: S = “ababababab”, P = 9 
Salida: 4 
El carácter en P es ‘a’. El número de ocurrencias de ‘a’ hasta el octavo índice es 4

Entrada: S = «geeksforgeeks», P = 9 
Salida: 1

Enfoque ingenuo: un enfoque ingenuo es iterar sobre la string hasta la Posición-1 en busca de un carácter similar. Siempre que ocurra un carácter similar, incremente la variable del contador en uno. 

A continuación se muestra la implementación del enfoque anterior:  

// CPP program to find the number of occurrences
// of a character at position P upto p-1
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the number of occurrences
// of a character at position P upto p-1
int Occurrence(string s, int position)
{
    int count = 0;
    for (int i = 0; i < position - 1; i++)
        if (s[i] == s[position - 1])
            count++;
 
    // Return the required count
    return count;
}
 
// Driver code
int main()
{
    string s = "ababababab";
 
    int p = 9;
 
    // Function call
    cout << Occurrence(s, p);
 
    return 0;
}

// Java program to find the number of occurrences
// of a character at position P upto p-1
class GFG
{
 
// Function to find the number of occurrences
// of a character at position P upto p-1
static int Occurrence(String s, int position)
{
    int count = 0;
    for (int i = 0; i < position - 1; i++)
        if (s.charAt(i) == s.charAt(position - 1))
            count++;
 
    // Return the required count
    return count;
}
 
// Driver code
public static void main(String[] args)
{
    String s = "ababababab";
 
    int p = 9;
 
    // Function call
    System.out.println(Occurrence(s, p));
}
}
 
// This code is contributed by 29AjayKumar

# Python3 program to find the
# number of occurrences of
# a character at position P upto p-1
 
# Function to find the number of occurrences
# of a character at position P upto p-1
def Occurrence(s, position):
    count = 0
    for i in range(position - 1):
        if (s[i] == s[position - 1]):
            count += 1
 
    # Return the required count
    return count
 
# Driver code
s = "ababababab";
 
p = 9
 
# Function call
print(Occurrence(s, p))
 
# This code is contributed by Mohit Kumar

// C# program to find the number of occurrences
// of a character at position P upto p-1
using System;
     
class GFG
{
 
// Function to find the number of occurrences
// of a character at position P upto p-1
static int Occurrence(String s, int position)
{
    int count = 0;
    for (int i = 0; i < position - 1; i++)
        if (s[i] == s[position - 1])
            count++;
 
    // Return the required count
    return count;
}
 
// Driver code
public static void Main(String[] args)
{
    String s = "ababababab";
 
    int p = 9;
 
    // Function call
    Console.WriteLine(Occurrence(s, p));
}
}
 
// This code is contributed by PrinciRaj1992

<script>
// Javascript program to find the number of occurrences
// of a character at position P upto p-1
 
// Function to find the number of occurrences
// of a character at position P upto p-1
function Occurrence(s,position)
{
    let count = 0;
    for (let i = 0; i < position - 1; i++)
        if (s[i] == s[position - 1])
            count++;
   
    // Return the required count
    return count;
}
 
// Driver code
let s = "ababababab";
   
let p = 9;
 
// Function call
document.write(Occurrence(s, p));
 
 
// This code is contributed by unknown2108
</script>

4

Complejidad de tiempo: O(N) para cada consulta.

Enfoque eficiente : en caso de que haya varias consultas de este tipo y se nos proporcione un índice P único para cada consulta, entonces un enfoque eficiente es utilizar una array de frecuencia para almacenar el recuento de caracteres en cada iteración de la string.

A continuación se muestra la implementación del enfoque anterior: 

// CPP program to find the number of occurrences
// of a character at position P upto p-1
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the number of occurrences
// of a character at position P upto p-1
int countOccurrence(string s, int position)
{
    int alpha[26] = { 0 }, b[s.size()] = { 0 };
 
    // Iterate over the string
    for (int i = 0; i < s.size(); i++) {
        // Store the Occurrence of same character
        b[i] = alpha[(int)s[i] - 97];
 
        // Increase its frequency
        alpha[(int)s[i] - 97]++;
    }
 
    // Return the required count
    return b[position - 1];
}
 
// Driver code
int main()
{
    string s = "ababababab";
 
    int p = 9;
 
    // Function call
    cout << countOccurrence(s, p);
 
    return 0;
}

// Java program to find the number of occurrences
// of a character at position P upto p-1
import java.util.*;
 
class GFG
{
 
// Function to find the number of occurrences
// of a character at position P upto p-1
static int countOccurrence(String s, int position)
{
    int []alpha = new int[26];
    int []b = new int[s.length()];
 
    // Iterate over the string
    for (int i = 0; i < s.length(); i++)
    {
        // Store the Occurrence of same character
        b[i] = alpha[(int)s.charAt(i) - 97];
 
        // Increase its frequency
        alpha[(int)s.charAt(i) - 97]++;
    }
 
    // Return the required count
    return b[position - 1];
}
 
// Driver code
public static void main(String[] args)
{
    String s = "ababababab";
 
    int p = 9;
 
    // Function call
    System.out.println(countOccurrence(s, p));
}
}
 
// This code is contributed by 29AjayKumar

# Python3 program to find the number of occurrences
# of a character at position P upto p-1
 
# Function to find the number of occurrences
# of a character at position P upto p-1
def countOccurrence(s, position):
    alpha = [0] * 26
    b = [0] * len(s)
     
    # Iterate over the string
    for i in range(0, len(s)):
         
        # Store the Occurrence of same character
        b[i] = alpha[ord(s[i]) - 97]
 
        # Increase its frequency
        alpha[ord(s[i]) - 97] = alpha[ord(s[i]) - 97] + 1
 
    # Return the required count
    return b[position - 1]
 
# Driver code
s = "ababababab"
 
p = 9
 
# Function call
print(countOccurrence(s, p))
 
# This code is contributed by Sanjit_Prasad

// C# program to find the number of occurrences
// of a character at position P upto p-1
using System;
     
class GFG
{
 
// Function to find the number of occurrences
// of a character at position P upto p-1
static int countOccurrence(String s, int position)
{
    int []alpha = new int[26];
    int []b = new int[s.Length];
 
    // Iterate over the string
    for (int i = 0; i < s.Length; i++)
    {
        // Store the Occurrence of same character
        b[i] = alpha[(int)s[i] - 97];
 
        // Increase its frequency
        alpha[(int)s[i] - 97]++;
    }
 
    // Return the required count
    return b[position - 1];
}
 
// Driver code
public static void Main(String[] args)
{
    String s = "ababababab";
 
    int p = 9;
 
    // Function call
    Console.WriteLine(countOccurrence(s, p));
}
}
 
// This code is contributed by PrinciRaj1992

<script>
 
// Javascript program to find the number of occurrences
// of a character at position P upto p-1
 
// Function to find the number of occurrences
// of a character at position P upto p-1
function countOccurrence(s, position)
{
    let alpha = new Array(26);
    for(let i = 0; i < 26; i++)
    {
        alpha[i] = 0;
    }
    let b = new Array(s.length);
  
    // Iterate over the string
    for(let i = 0; i < s.length; i++)
    {
         
        // Store the Occurrence of same character
        b[i] = alpha[s[i].charCodeAt(0) - 97];
  
        // Increase its frequency
        alpha[s[i].charCodeAt(0) - 97]++;
    }
  
    // Return the required count
    return b[position - 1];
}
 
// Driver code
let s = "ababababab";
 
p = 9;
 
// Function call
document.write(countOccurrence(s, p));
 
// This code is contributed by patel2127
 
</script>

4