Запросы на поиск последнего неповторяющегося символа в подстроке данной строки

Опубликовано: 5 Января, 2022

Для данной строки str задача состоит в том, чтобы ответить на Q запросов, где каждый запрос состоит из двух целых чисел L и R, и мы должны найти последний неповторяющийся символ в подстроке str [L… R] . Если нет неповторяющегося символа, выведите -1 .

Примеры:

Input: str = “GeeksForGeeks”, q[] = {{2, 9}, {2, 3}, {0, 12}}
Output:
G
k
r
Sub-string for the queries are “eksForGe”, “ek” and “GeeksForGeeks” and their last non-repeating characters are ‘G’, ‘k’ and ‘r’ respectively.
‘G’ is the first character from the end in given range which has frequency 1.

Input: str = “xxyyxx”, q[] = {{2, 3}, {3, 4}}
Output:
-1
x

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Подход: Создайте частотный массив freq [] [], где freq [i] [j] хранит частоту символа в подстроке str [0… j] , значение ASCII которой равно i . Теперь частота любого символа в подстроке str [i… j] , значение ASCII которой равно x, может быть вычислена как freq [x] [j] = freq [x] [i - 1] .
Теперь для каждого запроса начните обход строки в заданном диапазоне, то есть str [L… R], и для каждого символа, если его частота равна 1, то это последний неповторяющийся символ в требуемой подстроке. Если все символы имеют частоту больше 1, выведите -1 .

Ниже представлена реализация описанного выше подхода:

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 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 :
freq[ return 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 conributed 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 <
Technical Scripter

РЕКОМЕНДУЕМЫЕ СТАТЬИ

Количество чисел между L и R, взаимно простых с P
27 Февраля, 2023
Постройте матрицу, каждая строка и столбец которой содержат N и M единиц соответственно.
27 Февраля, 2023
Максимизируйте сумму трех чисел, выполнив побитовое XOR
27 Февраля, 2023
Проверьте, совпадает ли набор первых элементов X одного массива с набором первых элементов Y другого
27 Февраля, 2023
Подсчитать подстроки нечетной длины с медианой, такой же, как K-й символ строки
27 Февраля, 2023
Найти лексикографически первый идентификатор каждого домена из заданного массива идентификаторов электронной почты
27 Февраля, 2023
Найдите общее количество фигур 'X'
26 Февраля, 2023
Максимальное значение узла, которое может быть достигнуто с использованием данных соединений
26 Февраля, 2023