Count of bitonic substrings from the given string
Given a string str, the task is to count all the bitonic substrings of the given string.
A bitonic substring is a substring of the given string in which elements are either strictly increasing or strictly decreasing, or first increasing and then decreasing.
Examples:
Input: str = “bade”
Output: 8
Explanation:
Substrings of length 1 are always bitonic, “b”, “a”, “d”, “e”
Substrings of length 2 are “ba”, “ad”, “de” and these all are also bitonic because they are increasing or decreasing only.
Substrings of length 3 are “bad “and “ade” in which “ade” is bitonic.
Substring of length 4 “bade” is not bitonic because it decreases and then increases.
So total 8 substrings are bitonic.Input: str = “abc”
Output: 6
Explanation:
The given string is increasing, so all it’s substrings are also increasing and hence are bitonic. So total = 6.
Approach: The idea is to generate all possible substring of the given string and check if each substring is Bitonic or not. If the substring is Bitonic then increment the count for the answer. Finally, print the count of all the bitonic subarrays.
Below is the implementation of the above approach :
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
Time Complexity: O(N2)
Auxiliary Space: O(1)
Contact Us