Dada una string str , la tarea es contar todas las substrings bitónicas de la string dada.
Una substring bitónica es una substring de la string dada en la que los elementos son estrictamente crecientes o estrictamente decrecientes, o primero crecientes y luego decrecientes.
Ejemplos:
Entrada: str = “bade”
Salida: 8
Explicación: Las
substrings de longitud 1 siempre son bitónicas, “b”, “a”, “d”, “e”
Las substrings de longitud 2 son “ba”, “ad”, “de ” y todos estos también son bitónicos porque solo aumentan o disminuyen.
Las substrings de longitud 3 son «bad» y «ade» en las que «ade» es bitónico.
La substring de longitud 4 «bade» no es bitónica porque decrece y luego aumenta.
Entonces, un total de 8 substrings son bitónicas.Entrada: str = “abc”
Salida: 6
Explicación:
La string dada es creciente, por lo que todas sus substrings también son crecientes y, por lo tanto, son bitónicas. Entonces total = 6.
Enfoque: la idea es generar todas las substrings posibles de la string dada y verificar si cada substring es bitónica o no. Si la substring es bitónica, incremente el conteo de la respuesta. Finalmente, imprima el recuento de todos los subarreglos bitónicos.
A continuación se muestra la implementación del enfoque anterior:
C++
// C+++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find all the bitonic
// sub strings
void subString(char str[], int n)
{
// Pick starting point
int c = 0;
// Iterate till length of the string
for (int len = 1; len <= n; len++) {
// Pick ending point for string
for (int i = 0; i <= n - len; i++) {
// Substring from i to j
// is obtained
int j = i + len - 1;
char temp = str[i], f = 0;
// Substrings of length 1
if (j == i) {
// Increase count
c++;
continue;
}
int k = i + 1;
// For increasing sequence
while (temp < str[k] && k <= j) {
temp = str[k];
k++;
f = 2;
}
// Check for strictly increasing
if (k > j) {
// Increase count
c++;
f = 2;
}
// Check for decreasing sequence
while (temp > str[k]
&& k <= j
&& f != 2) {
k++;
f = 0;
}
if (k > j && f != 2) {
// Increase count
c++;
f = 0;
}
}
}
// Print the result
cout << c << endl;
}
// Driver Code
int main()
{
// Given string
char str[] = "bade";
// Function Call
subString(str, strlen(str));
return 0;
}
Java
// Java+ program for the above approach
import java.util.*;
class GFG{
// Function to find all the bitonic
// sub Strings
static void subString(char str[], int n)
{
// Pick starting point
int c = 0;
// Iterate till length of the String
for(int len = 1; len <= n; len++)
{
// Pick ending point for String
for(int i = 0; i <= n - len; i++)
{
// SubString from i to j
// is obtained
int j = i + len - 1;
char temp = str[i], f = 0;
// SubStrings of length 1
if (j == i)
{
// Increase count
c++;
continue;
}
int k = i + 1;
// For increasing sequence
while (k < n && temp < str[k])
{
temp = str[k];
k++;
f = 2;
}
// Check for strictly increasing
if (k > j)
{
// Increase count
c++;
f = 2;
}
// Check for decreasing sequence
while (k < n && temp > str[k] &&
f != 2)
{
k++;
f = 0;
}
if (k > j && f != 2)
{
// Increase count
c++;
f = 0;
}
}
}
// Print the result
System.out.print(c + "\n");
}
// Driver Code
public static void main(String[] args)
{
// Given String
char str[] = "bade".toCharArray();
// Function call
subString(str, str.length);
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program for the above approach # Function to find all the bitonic # sub strings def subString(str, n): # Pick starting po c = 0; # Iterate till length of the string for len in range(1, n + 1): # Pick ending point for string for i in range(0, n - len + 1): # Substring from i to j # is obtained j = i + len - 1; temp = str[i] f = 0; # Substrings of length 1 if (j == i): # Increase count c += 1 continue; k = i + 1; # For increasing sequence while (k <= j and temp < str[k]): temp = str[k]; k += 1; f = 2; # Check for strictly increasing if (k > j): # Increase count c += 1; f = 2; # Check for decreasing sequence while (k <= j and temp > str[k] and f != 2): k += 1; f = 0; if (k > j and f != 2): # Increase count c += 1; f = 0; # Print the result print(c) # Driver code # Given string str = "bade"; # Function Call subString(str, len(str)) # This code is contributed by grand_master
C#
// C# program for the above approach
using System;
class GFG{
// Function to find all the bitonic
// sub Strings
static void subString(char []str, int n)
{
// Pick starting point
int c = 0;
// Iterate till length of the String
for(int len = 1; len <= n; len++)
{
// Pick ending point for String
for(int i = 0; i <= n - len; i++)
{
// SubString from i to j
// is obtained
int j = i + len - 1;
char temp = str[i], f = (char)0;
// SubStrings of length 1
if (j == i)
{
// Increase count
c++;
continue;
}
int k = i + 1;
// For increasing sequence
while (k < n && temp < str[k])
{
temp = str[k];
k++;
f = (char)2;
}
// Check for strictly increasing
if (k > j)
{
// Increase count
c++;
f = (char)2;
}
// Check for decreasing sequence
while (k < n && temp > str[k] &&
f != 2)
{
k++;
f = (char)0;
}
if (k > j && f != 2)
{
// Increase count
c++;
f = (char)0;
}
}
}
// Print the result
Console.Write(c + "\n");
}
// Driver Code
public static void Main(String[] args)
{
// Given String
char []str = "bade".ToCharArray();
// Function call
subString(str, str.Length);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript program for the above approach
// Function to find all the bitonic
// sub strings
function subString(str, n)
{
// Pick starting point
var c = 0;
// Iterate till length of the string
for (var len = 1; len <= n; len++) {
// Pick ending point for string
for (var i = 0; i <= n - len; i++) {
// Substring from i to j
// is obtained
var j = i + len - 1;
var temp = str[i], f = 0;
// Substrings of length 1
if (j == i) {
// Increase count
c++;
continue;
}
var k = i + 1;
// For increasing sequence
while (temp < str[k] && k <= j) {
temp = str[k];
k++;
f = 2;
}
// Check for strictly increasing
if (k > j) {
// Increase count
c++;
f = 2;
}
// Check for decreasing sequence
while (temp > str[k]
&& k <= j
&& f != 2) {
k++;
f = 0;
}
if (k > j && f != 2) {
// Increase count
c++;
f = 0;
}
}
}
// Print the result
document.write( c );
}
// Driver Code
// Given string
var str = "bade".split('');
// Function Call
subString(str, str.length);
// This code is contributed by itsok.
</script>
8
Complejidad de Tiempo: O(N 2 )
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