Consultas para encontrar el último carácter no repetido en la substring de una string dada

Dada una string str , la tarea es responder consultas Q donde cada consulta consta de dos números enteros L y R y tenemos que encontrar el último carácter que no se repite en la substring str[L…R] . Si no hay ningún carácter que no se repita, imprima -1 .
Ejemplos: 
 

Entrada: str = “GeeksForGeeks”, q[] = {{2, 9}, {2, 3}, {0, 12}} Salida 
: 



La substring para las consultas es “eksForGe”, “ek” y “GeeksForGeeks” y sus últimos caracteres no repetidos son ‘G’, ‘k’ y ‘r’ respectivamente. 
‘G’ es el primer carácter desde el final en el rango dado que tiene frecuencia 1.
Entrada: str = “xxyyxx”, q[] = {{2, 3}, {3, 4}} 
Salida: 
-1 

 

Enfoque: Cree una array de frecuencia freq[][] donde freq[i][j] almacena la frecuencia del carácter en la substring str[0…j] cuyo valor ASCII es i . Ahora, la frecuencia de cualquier carácter en la substring str[i…j] cuyo valor ASCII es x se puede calcular como freq[x][j] = freq[x][i – 1]
Ahora, para cada consulta, comience a recorrer la string en el rango dado, es decir, str[L…R] y para cada carácter, si su frecuencia es 1 , entonces este es el último carácter que no se repite en la substring requerida. Si todos los caracteres tienen una frecuencia superior a 1 , imprima-1 .
A continuación se muestra la implementación del enfoque anterior: 
 

C++

// C++ implementation of the approach
#include<bits/stdc++.h>
using namespace std;
 
// Maximum distinct characters possible
int MAX = 256;
 
// To store the frequency of the characters
int freq[256][1000] = {0};
 
// Function to pre-calculate the frequency array
void preCalculate(string str, int n)
{
 
    // Only the first character has
    // frequency 1 till index 0
    freq[(int)str[0]][0] = 1;
 
    // Starting from the second
    // character of the string
    for (int i = 1; i < n; i++)
    {
        char ch = str[i];
 
        // For every possible character
        for (int j = 0; j < MAX; j++)
        {
 
            // Current character under consideration
            char charToUpdate = (char)j;
 
            // If it is equal to the character
            // at the current index
            if (charToUpdate == ch)
                freq[j][i] = freq[j][i - 1] + 1;
            else
                freq[j][i] = freq[j][i - 1];
        }
    }
}
 
// Function to return the frequency of the
// given character in the sub-string str[l...r]
int getFrequency(char ch, int l, int r)
{
 
    if (l == 0)
        return freq[(int)ch][r];
    else
        return (freq[(int)ch][r] - freq[(int)ch][l - 1]);
}
 
 
string getString(char x)
{
     
    // string class has a constructor
    // that allows us to specify size of
    // string as first parameter and character
    // to be filled in given size as second
    // parameter.
    string s(1, x);
 
    return s;
}
 
// Function to return the last non-repeating character
string lastNonRepeating(string str, int n, int l, int r)
{
 
    // Starting from the last character
    for (int i = r; i >= l; i--)
    {
 
        // Current character
        char ch = str[i];
 
        // If frequency of the current character is 1
        // then return the character
        if (getFrequency(ch, l, r) == 1)
            return getString(ch);
    }
 
    // All the characters of the
    // sub-string are repeating
    return "-1";
}
 
// Driver code
int main()
{
    string str = "GeeksForGeeks";
    int n = str.length();
 
    int queries[3][2] = { { 2, 9 }, { 2, 3 }, { 0, 12 } };
    int q =3;
 
    // Pre-calculate the frequency array
     
    preCalculate(str, n);
 
    for (int i = 0; i < q; i++)
    {
        cout << (lastNonRepeating(str, n,
                            queries[i][0],
                            queries[i][1]))<<endl;;
    }
}
 
// This code is contributed by Arnab Kundu

Java

// Java implementation of the approach
public class GFG {
 
    // Maximum distinct characters possible
    static final int MAX = 256;
 
    // To store the frequency of the characters
    static int freq[][];
 
    // Function to pre-calculate the frequency array
    static void preCalculate(String str, int n)
    {
 
        // Only the first character has
        // frequency 1 till index 0
        freq[(int)str.charAt(0)][0] = 1;
 
        // Starting from the second
        // character of the string
        for (int i = 1; i < n; i++) {
            char ch = str.charAt(i);
 
            // For every possible character
            for (int j = 0; j < MAX; j++) {
 
                // Current character under consideration
                char charToUpdate = (char)j;
 
                // If it is equal to the character
                // at the current index
                if (charToUpdate == ch)
                    freq[j][i] = freq[j][i - 1] + 1;
                else
                    freq[j][i] = freq[j][i - 1];
            }
        }
    }
 
    // Function to return the frequency of the
    // given character in the sub-string str[l...r]
    static int getFrequency(char ch, int l, int r)
    {
 
        if (l == 0)
            return freq[(int)ch][r];
        else
            return (freq[(int)ch][r] - freq[(int)ch][l - 1]);
    }
 
    // Function to return the last non-repeating character
    static String lastNonRepeating(String str, int n, int l, int r)
    {
 
        // Starting from the last character
        for (int i = r; i >= l; i--) {
 
            // Current character
            char ch = str.charAt(i);
 
            // If frequency of the current character is 1
            // then return the character
            if (getFrequency(ch, l, r) == 1)
                return ("" + ch);
        }
 
        // All the characters of the
        // sub-string are repeating
        return "-1";
    }
 
    // Driver code
    public static void main(String[] args)
    {
        String str = "GeeksForGeeks";
        int n = str.length();
 
        int queries[][] = { { 2, 9 }, { 2, 3 }, { 0, 12 } };
        int q = queries.length;
 
        // Pre-calculate the frequency array
        freq = new int[MAX][n];
        preCalculate(str, n);
 
        for (int i = 0; i < q; i++) {
            System.out.println(lastNonRepeating(str, n,
                                                queries[i][0],
                                                queries[i][1]));
        }
    }
}

Python3

# Python3 implementation of the approach
 
# Maximum distinct characters possible
MAX = 256
 
# To store the frequency of the characters
freq = [[0 for i in range(256)]
           for j in range(1000)]
 
# Function to pre-calculate
# the frequency array
def preCalculate(string, n):
 
    # Only the first character has
    # frequency 1 till index 0
    freq[ord(string[0])][0] = 1
 
    # Starting from the second
    # character of the string
    for i in range(1, n):
        ch = string[i]
 
        # For every possible character
        for j in range(MAX):
 
            # Current character under consideration
            charToUpdate = chr(j)
 
            # If it is equal to the character
            # at the current index
            if charToUpdate == ch:
                freq[j][i] = freq[j][i - 1] + 1
            else:
                freq[j][i] = freq[j][i - 1]
 
# Function to return the frequency of the
# given character in the sub-string str[l...r]
def getFrequency(ch, l, r):
    if l == 0:
        return freq[ord(ch)][r]
    else:
        return (freq[ord(ch)][r] -
                freq[ord(ch)][l - 1])
 
# Function to return the
# last non-repeating character
def lastNonRepeating(string, n, l, r):
 
    # Starting from the last character
    for i in range(r, l - 1, -1):
 
        # Current character
        ch = string[i]
 
        # If frequency of the current character is 1
        # then return the character
        if getFrequency(ch, l, r) == 1:
            return ch
 
    # All the characters of the
    # sub-string are repeating
    return "-1"
 
# Driver Code
if __name__ == "__main__":
    string = "GeeksForGeeks"
    n = len(string)
 
    queries = [(2, 9), (2, 3), (0, 12)]
    q = len(queries)
 
    # Pre-calculate the frequency array
    preCalculate(string, n)
 
    for i in range(q):
        print(lastNonRepeating(string, n,
                               queries[i][0],
                               queries[i][1]))
 
# This code is contributed by
# sanjeev2552

C#

// C# implementation of the approach
using System;
 
class GFG
{
 
    // Maximum distinct characters possible
    static int MAX = 256;
 
    // To store the frequency of the characters
    static int [,]freq;
 
    // Function to pre-calculate the frequency array
    static void preCalculate(string str, int n)
    {
 
        // Only the first character has
        // frequency 1 till index 0
        freq[(int)str[0],0] = 1;
 
        // Starting from the second
        // character of the string
        for (int i = 1; i < n; i++)
        {
            char ch = str[i];
 
            // For every possible character
            for (int j = 0; j < MAX; j++)
            {
 
                // Current character under consideration
                char charToUpdate = (char)j;
 
                // If it is equal to the character
                // at the current index
                if (charToUpdate == ch)
                    freq[j, i] = freq[j, i - 1] + 1;
                else
                    freq[j, i] = freq[j, i - 1];
            }
        }
    }
 
    // Function to return the frequency of the
    // given character in the sub-string str[l...r]
    static int getFrequency(char ch, int l, int r)
    {
 
        if (l == 0)
            return freq[(int)ch, r];
        else
            return (freq[(int)ch, r] - freq[(int)ch, l - 1]);
    }
 
    // Function to return the last non-repeating character
    static String lastNonRepeating(string str, int n, int l, int r)
    {
 
        // Starting from the last character
        for (int i = r; i >= l; i--)
        {
 
            // Current character
            char ch = str[i];
 
            // If frequency of the current character is 1
            // then return the character
            if (getFrequency(ch, l, r) == 1)
                return ("" + ch);
        }
 
        // All the characters of the
        // sub-string are repeating
        return "-1";
    }
 
    // Driver code
    public static void Main()
    {
        string str = "GeeksForGeeks";
        int n = str.Length;
 
        int [,]queries = { { 2, 9 }, { 2, 3 }, { 0, 12 } };
        int q = queries.Length;
 
        // Pre-calculate the frequency array
        freq = new int[MAX,n];
        preCalculate(str, n);
 
        for (int i = 0; i < q; i++)
        {
            Console.WriteLine(lastNonRepeating(str, n,
                                                queries[i,0],
                                                queries[i,1]));
        }
    }
}
 
// This code is contributed by AnkitRai01

PHP

<?php
// PHP implementation of the approach
 
// Maximum distinct characters possible
$MAX = 256;
 
// To store the frequency of the characters
$freq = array_fill(0, 256, array_fill(0, 1000, 0));
 
// Function to pre-calculate the frequency array
function preCalculate($str, $n)
{
     
    global $freq;
    global $MAX;
 
    // Only the first character has
    // frequency 1 till index 0
    $freq[ord($str[0])][0] = 1;
 
    // Starting from the second
    // character of the string
    for ($i = 1; $i < $n; $i++)
    {
        $ch = $str[$i];
 
        // For every possible character
        for ($j = 0; $j < $MAX; $j++)
        {
 
            // Current character under consideration
            $charToUpdate = chr($j);
 
            // If it is equal to the character
            // at the current index
            if ($charToUpdate == $ch)
                $freq[$j][$i] = $freq[$j][$i - 1] + 1;
            else
                $freq[$j][$i] = $freq[$j][$i - 1];
        }
    }
}
 
// Function to return the frequency of the
// given character in the sub-string $str[$l...$r]
function getFrequency($ch, $l, $r)
{
 
    global $freq;
    if ($l == 0)
        return $freq[ord($ch)][$r];
    else
        return ($freq[ord($ch)][$r] - $freq[ord($ch)][$l - 1]);
}
 
 
// Function to return the last non-repeating character
function lastNonRepeating($str, $n, $l, $r)
{
 
    // Starting from the last character
    for ($i = $r; $i >= $l; $i--)
    {
 
        // Current character
        $ch = $str[$i];
 
        // If frequency of the current character is 1
        // then return the character
        if (getFrequency($ch, $l, $r) == 1)
             return $ch;
    }
 
    // All the characters of the
    // sub-string are repeating
    return "-1";
}
 
// Driver code
 
$str = "GeeksForGeeks";
$n = strlen($str);
 
$queries = array( array( 2, 9 ), array( 2, 3 ), array( 0, 12 ) );
 
$q =3;
 
// Pre-calculate the frequency array
 
preCalculate($str, $n);
 
for ($i = 0; $i < $q; $i++)
{
    echo (lastNonRepeating($str, $n,
                        $queries[$i][0],
                        $queries[$i][1])), "\n";
}
 
 
// This code is contributed by ihritik
 
?>

Javascript

<script>
 
// JavaScript implementation of the approach
 
// Maximum distinct characters possible
    let MAX = 256;
     
     // To store the frequency of the characters
    let freq;
     
    // Function to pre-calculate the frequency array
     
    function preCalculate(str,n)
    {
        // Only the first character has
        // frequency 1 till index 0
        freq[str[0].charCodeAt(0)][0] = 1;
   
        // Starting from the second
        // character of the string
        for (let i = 1; i < n; i++) {
            let ch = str[i];
   
            // For every possible character
            for (let j = 0; j < MAX; j++) {
   
                // Current character under consideration
                let charToUpdate = String.fromCharCode(j);
   
                // If it is equal to the character
                // at the current index
                if (charToUpdate == ch)
                    freq[j][i] = freq[j][i - 1] + 1;
                else
                    freq[j][i] = freq[j][i - 1];
            }
        }
    }
     
    // Function to return the frequency of the
    // given character in the sub-string str[l...r]
    function getFrequency(ch,l,r)
    {
        if (l == 0)
            return freq[ch.charCodeAt(0)][r];
        else
            return (freq[ch.charCodeAt(0)][r] -
            freq[ch.charCodeAt(0)][l - 1]);
    }
     
    // Function to return the last non-repeating character
    function lastNonRepeating(str,n,l,r)
    {
        // Starting from the last character
        for (let i = r; i >= l; i--) {
   
            // Current character
            let ch = str[i];
   
            // If frequency of the current character is 1
            // then return the character
            if (getFrequency(ch, l, r) == 1)
                return ("" + ch);
        }
   
        // All the characters of the
        // sub-string are repeating
        return "-1";
    }
     
    // Driver code
    let str = "GeeksForGeeks";
    let n = str.length;
    let queries = [[ 2, 9 ], [ 2, 3 ], [ 0, 12 ]];
    let q = queries.length;
   
        // Pre-calculate the frequency array
        freq = new Array(MAX);
        for(let i=0;i<MAX;i++)
        {
            freq[i]=new Array(n);
            for(let j=0;j<n;j++)
            {
                freq[i][j]=0;
            }
        }
        preCalculate(str, n);
   
        for (let i = 0; i < q; i++) {
            document.write(
            lastNonRepeating(str, n,queries[i][0],queries[i][1])+
            "<br>");}
 
 
// This code is contributed by rag2127
 
</script>
Producción: 

G
k
r

 

Complejidad de tiempo: O (256 * N), ya que estamos usando bucles anidados para atravesar 256 * N veces. Donde N es la longitud de la string.

Espacio auxiliar: O(256*1000), ya que estamos usando espacio adicional para el mapa de frecuencias.

Publicación traducida automáticamente

Artículo escrito por 29AjayKumar 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 *