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