Dada una string S , la tarea es contar el número de substrings bitónicas inversas en la string dada.
Substring bitónica inversa: una string en la que los valores ASCII de los caracteres de la string siguen cualquiera de los siguientes patrones:
- estrictamente creciente
- estrictamente decreciente
- Disminuyendo y luego aumentando
Ejemplos:
Entrada: S = “bade”
Salida: 10
Explicación:
Todas las substrings posibles de longitud 1, {“b”, “a”, “d”, “e”} son siempre bitónicas inversas.
Las substrings de longitud 2 que son bitónicas inversas son {“ba”, “ad”, “de”}.
Las substrings de longitud 3 que son bitónicas inversas son {“bad”, “ade”}.
Solo la substring de longitud 4 que es bitónica inversa es «bade».
Por lo tanto, el recuento de substrings bitónicas inversas es 10.Entrada: S = “abc”
Salida: 6
Enfoque:
el enfoque es generar todas las substrings posibles de la string dada y seguir los pasos a continuación para cada substring para resolver el problema:
- Recorra la string y para cada carácter, verifique si el valor ASCII del siguiente carácter es menor que el valor ASCII del carácter actual o no.
- Si en algún momento, el valor ASCII del siguiente carácter es mayor que el valor ASCII del carácter actual, avance desde ese índice y para cada carácter de ahora en adelante, verifique si el valor ASCII del siguiente carácter es mayor que el valor ASCII del carácter actual o no.
- Si en algún momento, el valor ASCII del siguiente carácter es menor que el valor ASCII del carácter actual antes de llegar al final de la substring, entonces ignore la substring.
- Si se llega al final de la substring, aumente la cuenta .
- Después de completar todos los pasos anteriores para todas las substrings, imprima el valor final de count.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to calculate the number
// of reverse bitonic substrings
int CountsubString(char str[], int n)
{
// Stores the count
int c = 0;
// All possible lengths of substrings
for (int len = 1; len <= n; len++) {
// Starting point of a substring
for (int i = 0; i <= n - len; i++) {
// Ending point of a substring
int j = i + len - 1;
char temp = str[i], f = 0;
// Condition for reverse
// bitonic substrings of
// length 1
if (j == i) {
c++;
continue;
}
int k = i + 1;
// Check for decreasing sequence
while (temp > str[k] && k <= j) {
temp = str[k];
k++;
}
// If end of substring
// is reached
if (k > j) {
c++;
f = 2;
}
// For increasing sequence
while (temp < str[k] && k <= j
&& f != 2) {
temp = str[k];
k++;
}
// If end of substring
// is reached
if (k > j && f != 2) {
c++;
f = 0;
}
}
}
// Return the number
// of bitonic substrings
return c;
}
// Driver Code
int main()
{
char str[] = "bade";
cout << CountsubString(str, strlen(str));
return 0;
}
Java
// Java program to implement
// the above approach
class GFG{
// Function to calculate the number
// of reverse bitonic substrings
public static int CountsubString(char[] str,
int n)
{
// Stores the count
int c = 0;
// All possible lengths of substrings
for(int len = 1; len <= n; len++)
{
// Starting point of a substring
for(int i = 0; i <= n - len; i++)
{
// Ending point of a substring
int j = i + len - 1;
char temp = str[i], f = 0;
// Condition for reverse
// bitonic substrings of
// length 1
if (j == i)
{
c++;
continue;
}
int k = i + 1;
// Check for decreasing sequence
while (temp > str[k] && k <= j)
{
temp = str[k];
k++;
}
// If end of substring
// is reached
if (k > j)
{
c++;
f = 2;
}
// For increasing sequence
while (k <= j && temp < str[k] &&
f != 2)
{
temp = str[k];
k++;
}
// If end of substring
// is reached
if (k > j && f != 2)
{
c++;
f = 0;
}
}
}
// Return the number
// of bitonic substrings
return c;
}
// Driver code
public static void main(String[] args)
{
char str[] = { 'b', 'a', 'd', 'e' };
System.out.println(CountsubString(
str, str.length));
}
}
// This code is contributed by divyeshrabadiya07
Python3
# Python3 program to implement # the above approach # Function to calculate the number # of reverse bitonic substrings def CountsubString(strr, n): # Stores the count c = 0 # All possible lengths of substrings for len in range(n + 1): # Starting point of a substring for i in range(n - len): # Ending point of a substring j = i + len - 1 temp = strr[i] f = 0 # Condition for reverse # bitonic substrings of # length 1 if (j == i): c += 1 continue k = i + 1 # Check for decreasing sequence while (k <= j and temp > strr[k]): temp = strr[k] k += 1 # If end of substring # is reache if (k > j): c += 1 f = 2 # For increasing sequence while (k <= j and f != 2 and temp < strr[k]): temp = strr[k] k += 1 # If end of substring # is reached if (k > j and f != 2): c += 1 f = 0 # Return the number # of bitonic substrings return c # Driver Code if __name__ == '__main__': strr = "bade" print(CountsubString(strr, len(strr))) # This code is contributed by mohit kumar 29
C#
// C# program to implement
// the above approach
using System;
class GFG{
// Function to calculate the number
// of reverse bitonic substrings
public static int CountsubString(char[] str,
int n)
{
// Stores the count
int c = 0;
// All possible lengths of substrings
for(int len = 1; len <= n; len++)
{
// Starting point of a substring
for(int i = 0; i <= n - len; i++)
{
// Ending point of a substring
int j = i + len - 1;
char temp = str[i], f = '0';
// Condition for reverse
// bitonic substrings of
// length 1
if (j == i)
{
c++;
continue;
}
int k = i + 1;
// Check for decreasing sequence
while (temp > str[k] && k <= j)
{
temp = str[k];
k++;
}
// If end of substring
// is reached
if (k > j)
{
c++;
f = '2';
}
// For increasing sequence
while (k <= j && temp < str[k] &&
f != '2')
{
temp = str[k];
k++;
}
// If end of substring
// is reached
if (k > j && f != 2)
{
c++;
f = '0';
}
}
}
// Return the number
// of bitonic substrings
return c;
}
// Driver code
public static void Main(String[] args)
{
char []str = { 'b', 'a', 'd', 'e' };
Console.WriteLine(CountsubString(
str, str.Length) - 1);
}
}
// This code is contributed by amal kumar choubey
Javascript
<script>
// Javascript Program to implement
// the above approach
// Function to calculate the number
// of reverse bitonic substrings
function CountsubString(str, n)
{
// Stores the count
var c = 0;
// All possible lengths of substrings
for (var len = 1; len <= n; len++) {
// Starting point of a substring
for (var i = 0; i <= n - len; i++) {
// Ending point of a substring
var j = i + len - 1;
var temp = str[i], f = 0;
// Condition for reverse
// bitonic substrings of
// length 1
if (j == i) {
c++;
continue;
}
var k = i + 1;
// Check for decreasing sequence
while (temp > str[k] && k <= j) {
temp = str[k];
k++;
}
// If end of substring
// is reached
if (k > j) {
c++;
f = 2;
}
// For increasing sequence
while (temp < str[k] && k <= j
&& f != 2) {
temp = str[k];
k++;
}
// If end of substring
// is reached
if (k > j && f != 2) {
c++;
f = 0;
}
}
}
// Return the number
// of bitonic substrings
return c;
}
// Driver Code
var str = "bade".split('');
document.write( CountsubString(str, str.length));
// This code is contributed by importantly.
</script>
Producción:
10
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por grand_master y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA