Dada una array de caracteres alfanuméricos. La tarea es encontrar el subarreglo contiguo más largo que tenga el mismo número de letras (alfabetos) y números (dígitos numéricos). Imprime el índice inicial y final de este subarreglo. Si hay varios resultados, genera el que tenga el índice inicial más bajo.
Ejemplos:
Entrada: arr[] = {‘A’, ‘B’, ‘X’, ‘4’, ‘6’, ‘X’, ‘a’}
Salida: 1 4
El subarreglo requerido es {‘B’, ‘X’, ‘4’, ‘6’}.
{‘X’, ‘4’, ‘6’, ‘X’} también es un subconjunto válido de
longitud máxima pero su índice inicial no es el mínimo.
Entrada: arr[] = {‘1’, ‘2’, ‘a’, ‘b’, ‘c’, ‘1’, ‘n’, ‘c’, ‘1’, ‘2’}
Salida: 0 9
Enfoque: Tenemos que considerar el hecho de que todos los dígitos pueden tratarse de manera idéntica (lo que significa que 0 y 5 pueden tratarse como idénticos, pero 0 y ‘a’ no pueden tratarse de manera idéntica) y también todas las letras pueden tratarse de manera idéntica de manera similar. camino. Así que iteramos a través de la array y reemplazamos cada letra con ‘0’ y cada número con ‘1’.
Este problema luego se reduce a https://www.geeksforgeeks.org/largest-subarray-with-equal-number-of-0s-and-1s/ .
Después de modificar el código para que el algoritmo anterior cumpla con este problema, creamos el siguiente código para resolver el problema.
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 the starting and the
// ending index of the sub-array with equal
// number of alphabets and numeric digits
void findSubArray(int arr[], int n)
{
int sum = 0;
int maxsize = -1, startindex;
for (int i = 0; i < n; i++) {
// If its an alphabet
if (isalpha(arr[i])) {
arr[i] = 0;
}
// Else its a number
else {
arr[i] = 1;
}
}
// Pick a starting point as i
for (int i = 0; i < n - 1; i++) {
sum = (arr[i] == 0) ? -1 : 1;
// Consider all sub-arrays starting from i
for (int j = i + 1; j < n; j++) {
(arr[j] == 0) ? (sum += -1) : (sum += 1);
// If this is a 0 sum sub-array then
// compare it with maximum size sub-array
// calculated so far
if (sum == 0 && maxsize < j - i + 1) {
maxsize = j - i + 1;
startindex = i;
}
}
}
// If no valid sub-array found
if (maxsize == -1)
cout << maxsize;
else
cout << startindex << " " << (startindex + maxsize - 1);
}
// Driver code
int main()
{
int arr[] = { 'A', 'B', 'X', 4, 6, 'X', 'a' };
int size = sizeof(arr) / sizeof(arr[0]);
findSubArray(arr, size);
return 0;
}
Java
// Java implementation of the approach
class GFG
{
static boolean isalpha(int input_char)
{
if ((input_char >= 65 && input_char <= 90)
|| (input_char >= 97 && input_char <= 122))
return true;
return false;
}
// Function to find the starting and the
// ending index of the sub-array with equal
// number of alphabets and numeric digits
static void findSubArray(int arr[], int n)
{
int sum = 0;
int maxsize = -1, startindex = 0;
for (int i = 0; i < n; i++)
{
// If its an alphabet
if (isalpha(arr[i]))
{
arr[i] = 0;
}
// Else its a number
else
{
arr[i] = 1;
}
}
// Pick a starting point as i
for (int i = 0; i < n - 1; i++)
{
sum = (arr[i] == 0) ? -1 : 1;
// Consider all sub-arrays starting from i
for (int j = i + 1; j < n; j++)
{
if(arr[j] == 0)
sum += -1;
else
sum += 1;
// If this is a 0 sum sub-array then
// compare it with maximum size sub-array
// calculated so far
if (sum == 0 && maxsize < j - i + 1)
{
maxsize = j - i + 1;
startindex = i;
}
}
}
// If no valid sub-array found
if (maxsize == -1)
System.out.println(maxsize);
else
System.out.println(startindex + " " + (startindex + maxsize - 1));
}
// Driver code
public static void main (String[] args)
{
int arr[] = { 'A', 'B', 'X', 4, 6, 'X', 'a' };
int size = arr.length;
findSubArray(arr, size);
}
}
// This code is contributed by AnkitRai01
Python3
# Python3 implementation of the approach # Function to find the starting and the # ending index of the sub-array with equal # number of alphabets and numeric digits def findSubArray(arr, n): sum = 0 maxsize = -1 startindex=0 for i in range(n): # If its an alphabet if (arr[i].isalpha()): arr[i] = 0 # Else its a number else : arr[i] = 1 # Pick a starting point as i for i in range(n-1): if arr[i]=='1': sum=1 else: sum=-1 # Consider all sub-arrays starting from i for j in range(i+1,n): if arr[j]==0: sum-=1 else: sum+=1 # If this is a 0 sum sub-array then # compare it with maximum size sub-array # calculated so far if (sum == 0 and maxsize < j - i + 1) : maxsize = j - i + 1 startindex = i # If no valid sub-array found if (maxsize == -1): print(maxsize,end=" ") else: print(startindex,(startindex + maxsize - 1)) # Driver code arr=['A', 'B', 'X', '4', '6', 'X', 'a'] size =len(arr) findSubArray(arr, size) # This code is contributed by mohit kumar 29
C#
// C# implementation of the approach
using System;
class GFG
{
static bool isalpha(int input_char)
{
if ((input_char >= 65 && input_char <= 90)
|| (input_char >= 97 && input_char <= 122))
return true;
return false;
}
// Function to find the starting and the
// ending index of the sub-array with equal
// number of alphabets and numeric digits
static void findSubArray(int []arr, int n)
{
int sum = 0;
int maxsize = -1, startindex = 0;
for (int i = 0; i < n; i++)
{
// If its an alphabet
if (isalpha(arr[i]))
{
arr[i] = 0;
}
// Else its a number
else
{
arr[i] = 1;
}
}
// Pick a starting point as i
for (int i = 0; i < n - 1; i++)
{
sum = (arr[i] == 0) ? -1 : 1;
// Consider all sub-arrays starting from i
for (int j = i + 1; j < n; j++)
{
if(arr[j] == 0)
sum += -1;
else
sum += 1;
// If this is a 0 sum sub-array then
// compare it with maximum size sub-array
// calculated so far
if (sum == 0 && maxsize < j - i + 1)
{
maxsize = j - i + 1;
startindex = i;
}
}
}
// If no valid sub-array found
if (maxsize == -1)
Console.WriteLine(maxsize);
else
Console.WriteLine(startindex + " " + (startindex + maxsize - 1));
}
// Driver code
public static void Main()
{
int []arr = { 'A', 'B', 'X', 4, 6, 'X', 'a' };
int size = arr.Length;
findSubArray(arr, size);
}
}
// This code is contributed by anuj_67..
Javascript
<script>
// Javascript implementation of the approach
function isalpha(input_char)
{
if ((input_char >= 65 && input_char <= 90)
|| (input_char >= 97 && input_char <= 122))
return true;
return false;
}
// Function to find the starting and the
// ending index of the sub-array with equal
// number of alphabets and numeric digits
function findSubArray(arr, n)
{
let sum = 0;
let maxsize = -1, startindex = 0;
for (let i = 0; i < n; i++)
{
// If its an alphabet
if (isalpha(arr[i].charCodeAt()))
{
arr[i] = 0;
}
// Else its a number
else
{
arr[i] = 1;
}
}
// Pick a starting point as i
for (let i = 0; i < n - 1; i++)
{
sum = (arr[i] == 0) ? -1 : 1;
// Consider all sub-arrays starting from i
for (let j = i + 1; j < n; j++)
{
if(arr[j] == 0)
sum += -1;
else
sum += 1;
// If this is a 0 sum sub-array then
// compare it with maximum size sub-array
// calculated so far
if (sum == 0 && maxsize < j - i + 1)
{
maxsize = j - i + 1;
startindex = i;
}
}
}
// If no valid sub-array found
if (maxsize == -1)
document.write(maxsize + "</br>");
else
document.write(startindex + " " + (startindex + maxsize - 1) + "</br>");
}
let arr = [ 'A', 'B', 'X', '4', '6', 'X', 'a' ];
let size = arr.length;
findSubArray(arr, size);
</script>
1 4
Publicación traducida automáticamente
Artículo escrito por Ripunjoy Medhi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA