Dada una array de caracteres , str[] que consta de N alfabetos en minúsculas y una array de enteros, arr[] que consta de números en el rango [0, N – 1] . Las siguientes son las operaciones que se realizarán en el problema:
- Atraviese la array de caracteres str[] de izquierda a derecha.
- Para cada i -ésimo índice, almacene los intervalos de longitud impar más pequeños ( >1 ) (si existe), digamos [L, R] tal que str[L] = str[R] .
La tarea es encontrar el carácter lexicográficamente más pequeño de str[] que satisfaga exactamente una de las siguientes condiciones:
- No existen intervalos de longitud impares para el carácter donde str[L] == str[R] .
- Todos los intervalos del carácter deben contener un elemento de array indexado diferente.
Ejemplos:
Entrada: str[] = { ‘a’, ‘b’, ‘c’, ‘a’, ‘e’, ’a’, ‘a’ }, arr[] = { 4, 6 }
Salida: a
Explicación:
Los posibles intervalos de longitud impar más pequeños del carácter ‘a’ en str son { [0, 6], [3, 5] }
Dado que el intervalo [0, 6] contiene arr[1] y el intervalo [3, 5] contiene Arr[0]. Por lo tanto, la salida requerida es ‘a’.Entrada: str[] = { ‘a’, ‘b’, ‘c’, ‘d’ }, arr[] = { 3, 4 }
Salida: a
Explicación:
Dado que no existe ningún intervalo para ningún elemento de la array de caracteres. Por lo tanto, el carácter lexicográficamente más pequeño de str[] es ‘a’.Entrada: str[] = { ‘z’, ‘z’, ‘z’, ‘z’ }, arr[] = { 2 }
Salida: -1
Explicación:
Los posibles intervalos de longitud impar más pequeños del carácter ‘z’ son { [0, 2], [1, 3] }
Dado que el intervalo [0, 2] contiene arr[0] y el intervalo [1, 3] también contiene arr[0], que no es un elemento de array indexado distinto. Por lo tanto, la salida requerida es -1.
Enfoque: la idea es encontrar los intervalos de longitud impar más pequeños para todos los índices posibles de str[] . Recorra cada carácter distinto de str[] y compruebe si el carácter cumple o no las condiciones anteriores. Si más de un carácter satisface las condiciones anteriores, imprima el carácter lexicográficamente más pequeño de ellos. Siga los pasos a continuación para resolver el problema:
- Inicialice una array , digamos hash[] , para verificar si un carácter está presente en la array de caracteres, str[] o no.
- Inicialice una ArrayList , digamos intervals[] , de la forma { X, Y } para almacenar el punto inicial y final de los intervalos de longitud impar más pequeños.
- Recorra la array hash[] y almacene todos los intervalos de longitud impar más pequeños de cada carácter distinto de str[] .
- Ordenar intervalos[] en el orden creciente de X.
- Ordene la array arr[] en orden creciente .
- Compruebe que todos los intervalos de un carácter cumplen o no las condiciones anteriores realizando las siguientes operaciones:
- Inicialice un PriorityQueue , digamos, PQ para almacenar los intervalos en orden creciente de Y de los intervalos.
- Recorra la array arr[] de izquierda a derecha usando la variable i . Para cada i -ésimo índice de arr[] , recorra los intervalos[] usando la variable j y verifique si el punto de inicio de los intervalos[j] es menor que arr[i] o no. Si se encuentra que es cierto, inserte el intervalo en PQ .
- Si arr[i] está presente en un rango del intervalo, elimine el elemento superior de PQ para asegurarse de que los distintos elementos de la array indexada se asignen a diferentes intervalos.
- Si en algún momento arr[i] es menor que el punto final de los intervalos[i] o el punto final del elemento superior de PQ es menor que arr[i] , imprima -1 .
- De lo contrario, imprima el carácter lexicográficamente más pequeño de la array arr[] que satisfaga las condiciones.
A continuación se muestra la implementación del enfoque anterior:
Java
// Java Program to implement
// the above approach
import java.io.*;
import java.util.*;
class GFG {
// Structure of an interval
static class SpecialInterval {
// Stores start point of
// an interval
int low = 0;
// Stores end point of
// an interval
int high = 0;
// Initialize a interval
SpecialInterval(int low, int high)
{
this.low = low;
this.high = high;
}
}
// Function to check if a character
// present in arr[] or not
static boolean[] checkChar(char[] str)
{
// hash[i]: Check if character i
// is present in arr[] or not
boolean[] hash = new boolean[26];
// Traverse the character array
for (int i = 0; i < str.length; i++) {
// Mark arr[i] as true
hash[str[i] - 'a'] = true;
}
return hash;
}
// Function to check if all the intervals of a
// character satisfies the condition or not
private static boolean
checkIfValid(List<SpecialInterval> intervals,
int[] arr)
{
// If no intervals found for
// the current character
if (intervals.size() == 0) {
return true;
}
// Sort intervals on increasing
// order of start point
Collections.sort(intervals,
(interval1, interval2)
-> interval1.low - interval2.low);
// Store the intervals on increasing
// order of end point of interval
PriorityQueue<SpecialInterval> pq
= new PriorityQueue<SpecialInterval>(
intervals.size(),
(interval1, interval2)
-> interval1.high - interval2.high);
// Stores count of array elements that
// is present in different intervals
int count = 0;
// Stores index of an interval
int j = 0;
// Traverse the character array
for (int i = 0; i < arr.length
&& count < intervals.size();
i++) {
// Traverse intervals[] array
while (j < intervals.size()) {
// Stores interval
// at j-th index
SpecialInterval interval
= intervals.get(j);
// If start point of interval
// greater than arr[i]
if (interval.low > arr[i])
break;
// Update j
j++;
// Insert interval into pq
pq.offer(interval);
}
// If count of intervals
// in pq greater than 0
if (pq.size() > 0) {
// Stores top element of pq
SpecialInterval interval
= pq.poll();
// arr[i] does not lie in
// the range of the interval
if (arr[i] > interval.high) {
break;
}
// Update count
count++;
}
}
return count == intervals.size();
}
// Function to find the intervals
// for each distinct character of str[]
private static List<SpecialInterval>
findSpecialIntevals(char[] str, char ch)
{
// Stores the odd index
// of the character array
int oddPrev = -1;
// Stores even index of
// the character array
int evenPrev = -1;
// Stores all intervals for each
// distinct character of str
List<SpecialInterval> intervals
= new ArrayList<SpecialInterval>();
// Traverse the character array
for (int i = 0; i < str.length;
i++) {
if (str[i] == ch) {
// If i is even
if (i % 2 == 0) {
// If evenPrev not
// equal to -1
if (evenPrev == -1) {
// Update evenPrev
evenPrev = i;
}
else {
// Initialize an interval
SpecialInterval interval
= new SpecialInterval(
evenPrev, i);
// Insert current interval
// into intervals
intervals.add(interval);
// Update evenPrev
evenPrev = -1;
}
}
else {
// If oddPrev not
// equal to -1
if (oddPrev == -1) {
// Update oddPrev
oddPrev = i;
}
else {
// Initialize an interval
SpecialInterval interval
= new SpecialInterval(
oddPrev, i);
// Insert current interval
// into intervals
intervals.add(interval);
// Update oddPrev
oddPrev = -1;
}
}
}
}
return intervals;
}
// Function to print lexicographically smallest
// character that satisfies the condition
static void printAnswer(char[] str, int arr[])
{
// Sort the array
Arrays.sort(arr);
// Check if a character is present in
// str that satisfies the condition
boolean possible = false;
// hash[i]: Check if character i
// is present in arr[] or not
boolean[] hash = checkChar(str);
// Traverse all possible distinct
// character of str
for (int ch = 0; ch < 26; ch++) {
// If ch present in str
if (!hash[ch])
continue;
// Find all the intervals for
// current character
List<SpecialInterval> intervals
= findSpecialIntevals(str,
(char)(ch + 'a'));
// Update possible
possible
= checkIfValid(intervals, arr);
// If a character found in str that
// satisfies the condition
if (possible) {
System.out.println(
(char)(ch + 'a'));
break;
}
}
// If no character found that
// satisfies the condition
if (!possible)
System.out.println(-1);
}
// Driver Code
public static void main(String[] args)
{
char[] str = { 'a', 'b', 'c', 'a',
'e', 'a', 'a' };
int arr[] = { 4, 6 };
printAnswer(str, arr);
}
}
a
Complejidad de tiempo: O(N * log(N))
Espacio auxiliar: O(N)