Dada una string que consta solo de alfabetos ingleses en minúsculas. La tarea es contar el número total de caracteres alfabéticamente más pequeños en el lado derecho de los caracteres en cada índice.
Ejemplos:
Entrada: str = “edcba”
Salida: 4 3 2 1 0
Explicación:
El número de caracteres en el lado derecho del índice 0 que es más pequeño que
e son dcba = 4
El número de caracteres en el lado derecho del índice 1 que es más pequeño que
d son cba = 3
El número de caracteres en el lado derecho del índice 2 que es más pequeño que
c son ba = 2
El número de caracteres en el lado derecho del índice 3 que es más pequeño que
b son a = 1
El número de caracteres en el lado derecho del índice 4 que es más pequeño que un
área‘\0’ = 0Entrada: str = “eaaa”
Salida: 3 0 0 0
Enfoque ingenuo:
la idea es recorrer todos los caracteres en el lado derecho de cada índice de string uno por uno e imprimir el recuento de caracteres que son alfabéticamente más pequeños.
C++
#include <bits/stdc++.h>
using namespace std;
// function to count the smaller
// characters at the right of index i
void countSmaller(string str)
{
// store the length of string
int n = str.length();
for (int i = 0; i < n; i++) {
// for each index initialize
// count as zero
int cnt = 0;
for (int j = i + 1; j < n; j++) {
// increment the count if
// characters are smaller
// than at ith index
if (str[j] < str[i]) {
cnt += 1;
}
}
// print the count of characters
// smaller than the index i
cout << cnt << " ";
}
}
// Driver code
int main()
{
// input string
string str = "edcba";
countSmaller(str);
}
Java
class GFG
{
// function to count the smaller
// characters at the right of index i
static void countSmaller(String str)
{
// store the length of String
int n = str.length();
for (int i = 0; i < n; i++)
{
// for each index initialize
// count as zero
int cnt = 0;
for (int j = i + 1; j < n; j++)
{
// increment the count if
// characters are smaller
// than at ith index
if (str.charAt(j) < str.charAt(i))
{
cnt += 1;
}
}
// print the count of characters
// smaller than the index i
System.out.print(cnt+ " ");
}
}
// Driver code
public static void main(String[] args)
{
// input String
String str = "edcba";
countSmaller(str);
}
}
// This code is contributed by 29AjayKumar
Python3
# function to count the smaller # characters at the right of index i def countSmaller(str): # store the length of String n = len(str); for i in range(n): # for each index initialize # count as zero cnt = 0; for j in range(i + 1, n): # increment the count if # characters are smaller # than at ith index if (str[j] < str[i]): cnt += 1; # print the count of characters # smaller than the index i print(cnt, end =" "); # Driver code if __name__ == '__main__': # input String str = "edcba"; countSmaller(str); # This code is contributed by PrinciRaj1992
C#
using System;
class GFG
{
// function to count the smaller
// characters at the right of index i
static void countSmaller(String str)
{
// store the length of String
int n = str.Length;
for (int i = 0; i < n; i++)
{
// for each index initialize
// count as zero
int cnt = 0;
for (int j = i + 1; j < n; j++)
{
// increment the count if
// characters are smaller
// than at ith index
if (str[j] < str[i])
{
cnt += 1;
}
}
// print the count of characters
// smaller than the index i
Console.Write(cnt+ " ");
}
}
// Driver code
public static void Main(String[] args)
{
// input String
String str = "edcba";
countSmaller(str);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// function to count the smaller
// characters at the right of index i
function countSmaller(str)
{
// store the length of string
var n = str.length;
for (var i = 0; i < n; i++) {
// for each index initialize
// count as zero
var cnt = 0;
for (var j = i + 1; j < n; j++) {
// increment the count if
// characters are smaller
// than at ith index
if (str[j] < str[i]) {
cnt += 1;
}
}
// print the count of characters
// smaller than the index i
document.write( cnt + " ");
}
}
// Driver code
// input string
var str = "edcba";
countSmaller(str);
</script>
4 3 2 1 0
Complejidad de tiempo: O( N 2 ), donde N = longitud de la string
Espacio auxiliar: O(1)
Mejor enfoque: la idea es usar BST de autoequilibrio.
Se puede utilizar un árbol de búsqueda binario autoequilibrado (AVL, Red Black, .. etc.) para obtener la solución en una complejidad de tiempo O (N log N). Podemos aumentar estos árboles para que cada Node N contenga el tamaño del subárbol enraizado con N. Hemos utilizado el árbol AVL en la siguiente implementación.
Atravesamos la string de derecha a izquierda e insertamos todos los elementos uno por uno en un árbol AVL. Al insertar una nueva clave en un árbol AVL, primero comparamos la clave con la raíz. Si la clave es mayor que la raíz, entonces es mayor que todos los Nodes del subárbol izquierdo de la raíz. Entonces agregamos el tamaño del subárbol izquierdo al conteo de elementos más pequeños para la clave que se está insertando. Seguimos recursivamente el mismo enfoque para todos los Nodes de la raíz.
Consulte este artículo para la implementación del enfoque anterior.
Complejidad de tiempo: O( N*log N )
Espacio auxiliar: O( N )
Enfoque eficiente:
la idea es usar técnicas de hashing porque la string consta solo de letras en minúsculas. Así que aquí podemos tomar una array de tamaño 26 que se usa para almacenar el recuento de caracteres más pequeños en el lado derecho de ese índice.
Recorra la array desde la derecha y siga actualizando el recuento de caracteres en la array hash. Ahora, para encontrar el conteo de caracteres más pequeños a la derecha, simplemente podemos atravesar la array hash de tamaño 26 cada vez para contar los caracteres más pequeños encontrados hasta ahora.
C++
#include <bits/stdc++.h>
using namespace std;
// Function to count the smaller
// characters on the right of index i
void countSmaller(string str)
{
// store the length of string
int n = str.length();
// initialize each elements of
// arr to zero
int arr[26] = { 0 };
// array to store count of smaller characters on
// the right side of that index
int ans[n];
for (int i = n - 1; i >= 0; i--) {
arr[str[i] - 'a']++;
// initialize the variable to store
// the count of characters smaller
// than that at index i
int ct = 0;
// adding the count of characters
// smaller than index i
for (int j = 0; j < str[i] - 'a'; j++) {
ct += arr[j];
}
ans[i] = ct;
}
// print the count of characters smaller
// than index i stored in ans array
for (int i = 0; i < n; i++) {
cout << ans[i] << " ";
}
}
// Driver Code
int main()
{
string str = "edcbaa";
countSmaller(str);
return 0;
}
Java
class GFG
{
// Function to count the smaller
// characters on the right of index i
static void countSmaller(String str)
{
// store the length of String
int n = str.length();
// initialize each elements of
// arr to zero
int arr[] = new int[26];
// array to store count of smaller characters on
// the right side of that index
int ans[] = new int[n];
for (int i = n - 1; i >= 0; i--)
{
arr[str.charAt(i) - 'a']++;
// initialize the variable to store
// the count of characters smaller
// than that at index i
int ct = 0;
// adding the count of characters
// smaller than index i
for (int j = 0; j < str.charAt(i) - 'a'; j++)
{
ct += arr[j];
}
ans[i] = ct;
}
// print the count of characters smaller
// than index i stored in ans array
for (int i = 0; i < n; i++)
{
System.out.print(ans[i] + " ");
}
}
// Driver Code
public static void main(String[] args)
{
String str = "edcbaa";
countSmaller(str);
}
}
// This code is contributed by 29AjayKumar
Python3
# Function to count the smaller
# characters on the right of index i
def countSmaller(str):
# store the length of String
n = len(str);
# initialize each elements of
# arr to zero
arr = [0]*26;
# array to store count of smaller characters on
# the right side of that index
ans = [0]*n;
for i in range(n - 1, -1, -1):
arr[ord(str[i] ) - ord('a')] += 1;
# initialize the variable to store
# the count of characters smaller
# than that at index i
ct = 0;
# adding the count of characters
# smaller than index i
for j in range(ord(str[i] ) - ord('a')):
ct += arr[j];
ans[i] = ct;
# print the count of characters smaller
# than index i stored in ans array
for i in range(n):
print(ans[i], end = " ");
# Driver Code
if __name__ == '__main__':
str = "edcbaa";
countSmaller(str);
# This code is contributed by Rajput-Ji
C#
using System;
class GFG
{
// Function to count the smaller
// characters on the right of index i
static void countSmaller(String str)
{
// store the length of String
int n = str.Length;
// initialize each elements of
// arr to zero
int []arr = new int[26];
// array to store count of smaller characters on
// the right side of that index
int []ans = new int[n];
for (int i = n - 1; i >= 0; i--)
{
arr[str[i] - 'a']++;
// initialize the variable to store
// the count of characters smaller
// than that at index i
int ct = 0;
// adding the count of characters
// smaller than index i
for (int j = 0; j < str[i] - 'a'; j++)
{
ct += arr[j];
}
ans[i] = ct;
}
// print the count of characters smaller
// than index i stored in ans array
for (int i = 0; i < n; i++)
{
Console.Write(ans[i] + " ");
}
}
// Driver Code
public static void Main(String[] args)
{
String str = "edcbaa";
countSmaller(str);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Function to count the smaller
// characters on the right of index i
function countSmaller(str)
{
// store the length of string
var n = str.length;
// initialize each elements of
// arr to zero
var arr = Array(26).fill(0);
// array to store count of smaller characters on
// the right side of that index
var ans = Array(n);
for (var i = n - 1; i >= 0; i--) {
arr[str[i].charCodeAt(0) - 'a'.charCodeAt(0)]++;
// initialize the variable to store
// the count of characters smaller
// than that at index i
var ct = 0;
// adding the count of characters
// smaller than index i
for (var j = 0; j < str[i].charCodeAt(0) - 'a'.charCodeAt(0); j++) {
ct += arr[j];
}
ans[i] = ct;
}
// print the count of characters smaller
// than index i stored in ans array
for (var i = 0; i < n; i++) {
document.write( ans[i] + " ");
}
}
// Driver Code
var str = "edcbaa";
countSmaller(str);
</script>
5 4 3 2 0 0
Complejidad de Tiempo: O(N*26)
Espacio Auxiliar: O(N+26)