Dada la string str de longitud N, la tarea es imprimir el número de substrings en las que el valor ASCII de cada carácter es mayor o igual que el valor ASCII del carácter anterior. Las substrings deben tener al menos una longitud de 2.
Ejemplo :
Entrada : str = “bcdabc”
Salida : 6
Explicación : Las 6 substrings con letras que tienen un valor ASCII mayor que el carácter anterior y una longitud de al menos 2 son bc, bcd, cd, ab, abc, bcEntrada : str = “cegxza”
Salida : 10
Enfoque ingenuo : el problema anterior puede ser iterar la string y contar las substrings de valores ASCII crecientes que comienzan en cada índice.
Complejidad del tiempo: O(N^2)
Enfoque: un enfoque eficiente para el problema dado sería iterar la string y usar un cálculo matemático para encontrar todas las substrings de valores ASCII crecientes posibles en una substring más grande. Siga el siguiente enfoque para resolver el problema:
- Inicialice los punteros izquierdo y derecho a 0
- Inicializar una variable y almacenar la respuesta
- Itere la string hasta que el puntero derecho sea menor que la longitud de la string:
- Use un ciclo while para iterar usando el puntero derecho hasta que str[right] >= str[right – 1] y right < str.length()
- Calcule la cantidad de substrings que tienen un valor ASCII creciente agregando la inicialización len = derecha – izquierda, luego agregando el valor de (len * (len + 1) / 2) – len a ans
- Haga izquierda = derecha y el puntero derecho se incrementará para la próxima iteración
- Regresar como nuestro resultado
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to count number of substrings
// with increasing ascii values
int countIncSub(string str)
{
// Initialize left and right pointers
int left = 0, right = 1;
// Initialize length of the string str
int l = str.length();
// Initialize a variable to store answer
int ans = 0;
// Iterate the string
for (; right < l; right++)
{
// Iterate the while loop until the
// string has increasing ASCII value
while (right < l && str[right] >= str[right - 1])
{
right++;
}
// Calculate length of longest
// substring found starting from left
int len = right - left;
// Calculate the number of substrings
// with length at least 2 and add it
// to the ans
ans += (len * (len + 1)) / 2 - len;
// Update left equal to right
left = right;
}
// Return the answer
return ans;
}
int main()
{
// Initialize the string str
string str = "cegxza";
// Call the function and
// print the result
cout << (countIncSub(str));
}
// This code is contributed by Potta Lokesh
Java
// Java implementation for the above approach
import java.io.*;
import java.util.*;
// Driver code
class GFG {
// Function to count number of substrings
// with increasing ascii values
public static int countIncSub(String str)
{
// Initialize left and right pointers
int left = 0, right = 1;
// Initialize length of the string str
int l = str.length();
// Initialize a variable to store answer
int ans = 0;
// Iterate the string
for (; right < l; right++) {
// Iterate the while loop until the
// string has increasing ASCII value
while (right < l
&& str.charAt(right)
>= str.charAt(right - 1)) {
right++;
}
// Calculate length of longest
// substring found starting from left
int len = right - left;
// Calculate the number of substrings
// with length at least 2 and add it
// to the ans
ans += (len * (len + 1)) / 2 - len;
// Update left equal to right
left = right;
}
// Return the answer
return ans;
}
public static void main(String[] args)
{
// Initialize the string str
String str = "cegxza";
// Call the function and
// print the result
System.out.println(countIncSub(str));
}
}
Python3
# Python code for the above approach # Function to count number of substrings # with increasing ascii values def countIncSub(str): # Initialize left and right pointers left = 0 right = 1 # Initialize length of the string str l = len(str) # Initialize a variable to store answer ans = 0 # Iterate the string for right in range(1, l): # Iterate the while loop until the # string has increasing ASCII value while (right < l and str[right] >= str[right - 1]): right += 1 # Calculate length of longest # substring found starting from left length = right - left # Calculate the number of substrings # with length at least 2 and add it # to the ans ans += (length * (length + 1)) // 2 - length # Update left equal to right left = right # Return the answer return ans # Driver Code # Initialize the string str str = "cegxza" # Call the function and # print the result print(countIncSub(str)) # This code is contributed by Saurabh Jaiswal
C#
// C# implementation for the above approach
using System;
using System.Collections;
// Driver code
class GFG {
// Function to count number of substrings
// with increasing ascii values
static int countIncSub(string str)
{
// Initialize left and right pointers
int left = 0, right = 1;
// Initialize length of the string str
int l = str.Length;
// Initialize a variable to store answer
int ans = 0;
// Iterate the string
for (; right < l; right++) {
// Iterate the while loop until the
// string has increasing ASCII value
while (right < l
&& str[right]
>= str[right - 1]) {
right++;
}
// Calculate length of longest
// substring found starting from left
int len = right - left;
// Calculate the number of substrings
// with length at least 2 and add it
// to the ans
ans += (len * (len + 1)) / 2 - len;
// Update left equal to right
left = right;
}
// Return the answer
return ans;
}
public static void Main()
{
// Initialize the string str
string str = "cegxza";
// Call the function and
// print the result
Console.Write(countIncSub(str));
}
}
// This code is contributed by Samim Hossain Mondal
Javascript
<script>
// Javascript code for the above approach
// Function to count number of substrings
// with increasing ascii values
function countIncSub(str)
{
// Initialize left and right pointers
let left = 0, right = 1;
// Initialize length of the string str
let l = str.length;
// Initialize a variable to store answer
let ans = 0;
// Iterate the string
for (; right < l; right++)
{
// Iterate the while loop until the
// string has increasing ASCII value
while (right < l && str[right] >= str[right - 1])
{
right++;
}
// Calculate length of longest
// substring found starting from left
let len = right - left;
// Calculate the number of substrings
// with length at least 2 and add it
// to the ans
ans += (len * (len + 1)) / 2 - len;
// Update left equal to right
left = right;
}
// Return the answer
return ans;
}
// Driver Code
// Initialize the string str
let str = "cegxza";
// Call the function and
// print the result
document.write(countIncSub(str));
// This code is contributed by Samim Hossain Mondal
</script>
Producción:
10
Complejidad temporal : O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por kartikmodi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA