Recuento de substrings bitónicas inversas en una string dada

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *