Given a string str, the task is to find the minimum numbers of substrings that the given string S can be split into, such that each substring is monotonously increasing or decreasing.
Examples:
Input: str = “abcdcba”
Output: 2
Explanation:
The string can be split into a minimum of 2 monotonous substrings {“abcd”(increasing), “cba”(decreasing)}
Input: str = “aeccdhba”
Output: 3
Explanation:
The generated substrings are {“ae”, “ccdh”, “ba”}
Approach: Follow the steps below to solve the problem:
- Initialize a variable ongoing = ‘N’ to keep track of order of current sequence.
- Iterate over the string and for each character, follow the steps below:
- If ongoing == ‘N’:
- If curr_character < prev_character then update ongoing with D(Non-Increasing).
- Otherwise, if curr_character > prev_character, then update ongoing with I(Non-Decreasing).
- Otherwise, update ongoing with N(neither Non-Increasing nor Non-Decreasing).
- Otherwise, if ongoing == ‘I’:
- If curr_character > prev_character then update ongoing with I.
- Otherwise, if curr_character < prev_character then update ongoing with N and increment answer.
- Otherwise, update ongoing with I.
- else do the following steps:
- If curr_character < prev_character then update ongoing with D.
- Otherwise, if curr_character > prev_character then update ongoing with N and increment answer.
- Otherwise, update ongoing with D.
- Finally, print answer+1 is the required answer.
Below is the implementation of the above approach:
C++
// C++ program to implement// the above approach#include<bits/stdc++.h>using namespace std;// Function to return final resultint minReqSubstring(string s, int n){ // Initialize variable to keep // track of ongoing sequence char ongoing = 'N'; int count = 0, l = s.size(); for(int i = 1; i < l; i++) { // If current sequence is neither // increasing nor decreasing if (ongoing == 'N') { // If prev char is greater if (s[i] < s[i - 1]) { ongoing = 'D'; } // If prev char is same else if (s[i] == s[i - 1]) { ongoing = 'N'; } // Otherwise else { ongoing = 'I'; } } // If current sequence // is Non-Decreasing else if (ongoing == 'I') { // If prev char is smaller if (s[i] > s[i - 1]) { ongoing = 'I'; } // If prev char is same else if (s[i] == s[i - 1]) { // Update ongoing ongoing = 'I'; } // Otherwise else { // Update ongoing ongoing = 'N'; // Increase count count += 1; } } // If current sequence // is Non-Increasing else { // If prev char is greater, // then update ongoing with D if (s[i] < s[i - 1]) { ongoing = 'D'; } // If prev char is equal, then // update current with D else if (s[i] == s[i - 1]) { ongoing = 'D'; } // Otherwise, update ongoing // with N and increment count else { ongoing = 'N'; count += 1; } } } // Return count+1 return count + 1;}// Driver Codeint main(){ string S = "aeccdhba"; int n = S.size(); cout << (minReqSubstring(S, n)); return 0;}// This code is contributed by Amit Katiyar |
Java
// Java Program to implement// the above approachimport java.util.*;class GFG { // Function to return final result static int minReqSubstring(String s, int n) { // Initialize variable to keep // track of ongoing sequence char ongoing = 'N'; int count = 0, l = s.length(); for (int i = 1; i < l; i++) { // If current sequence is neither // increasing nor decreasing if (ongoing == 'N') { // If prev char is greater if (s.charAt(i) < s.charAt(i - 1)) { ongoing = 'D'; } // If prev char is same else if (s.charAt(i) == s.charAt(i - 1)) { ongoing = 'N'; } // Otherwise else { ongoing = 'I'; } } // If current sequence // is Non-Decreasing else if (ongoing == 'I') { // If prev char is smaller if (s.charAt(i) > s.charAt(i - 1)) { ongoing = 'I'; } // If prev char is same else if (s.charAt(i) == s.charAt(i - 1)) { // Update ongoing ongoing = 'I'; } // Otherwise else { // Update ongoing ongoing = 'N'; // Increase count count += 1; } } // If current sequence // is Non-Increasing else { // If prev char is greater, // then update ongoing with D if (s.charAt(i) < s.charAt(i - 1)) { ongoing = 'D'; } // If prev char is equal, then // update current with D else if (s.charAt(i) == s.charAt(i - 1)) { ongoing = 'D'; } // Otherwise, update ongoing // with N and increment count else { ongoing = 'N'; count += 1; } } } // Return count+1 return count + 1; } // Driver Code public static void main(String[] args) { String S = "aeccdhba"; int n = S.length(); System.out.print( minReqSubstring(S, n)); }} |
Python3
# Python3 program to implement # the above approach # Function to return final result def minReqSubstring(s, n): # Initialize variable to keep # track of ongoing sequence ongoing = 'N' count, l = 0, len(s) for i in range(1, l): # If current sequence is neither # increasing nor decreasing if ongoing == 'N': # If prev char is greater if s[i] < s[i - 1]: ongoing = 'D' # If prev char is same elif s[i] == s[i - 1]: ongoing = 'N' # Otherwise else: ongoing = 'I' # If current sequence # is Non-Decreasing elif ongoing == 'I': # If prev char is smaller if s[i] > s[i - 1]: ongoing = 'I' # If prev char is same elif s[i] == s[i - 1]: # Update ongoing ongoing = 'I' # Otherwise else: # Update ongoing ongoing = 'N' # Increase count count += 1 # If current sequence # is Non-Increasing else: # If prev char is greater, # then update ongoing with D if s[i] < s[i - 1]: ongoing = 'D' # If prev char is equal, then # update current with D elif s[i] == s[i - 1]: ongoing = 'D' # Otherwise, update ongoing # with N and increment count else: ongoing = 'N' count += 1 # Return count + 1 return count + 1# Driver codeS = "aeccdhba"n = len(S)print(minReqSubstring(S, n))# This code is contributed by Stuti Pathak |
C#
// C# Program to implement// the above approachusing System;class GFG{ // Function to return readonly result static int minReqSubstring(String s, int n) { // Initialize variable to keep // track of ongoing sequence char ongoing = 'N'; int count = 0, l = s.Length; for (int i = 1; i < l; i++) { // If current sequence is neither // increasing nor decreasing if (ongoing == 'N') { // If prev char is greater if (s[i] < s[i - 1]) { ongoing = 'D'; } // If prev char is same else if (s[i] == s[i - 1]) { ongoing = 'N'; } // Otherwise else { ongoing = 'I'; } } // If current sequence // is Non-Decreasing else if (ongoing == 'I') { // If prev char is smaller if (s[i] > s[i - 1]) { ongoing = 'I'; } // If prev char is same else if (s[i] == s[i - 1]) { // Update ongoing ongoing = 'I'; } // Otherwise else { // Update ongoing ongoing = 'N'; // Increase count count += 1; } } // If current sequence // is Non-Increasing else { // If prev char is greater, // then update ongoing with D if (s[i] < s[i - 1]) { ongoing = 'D'; } // If prev char is equal, then // update current with D else if (s[i] == s[i - 1]) { ongoing = 'D'; } // Otherwise, update ongoing // with N and increment count else { ongoing = 'N'; count += 1; } } } // Return count+1 return count + 1; } // Driver Code public static void Main(String[] args) { String S = "aeccdhba"; int n = S.Length; Console.Write(minReqSubstring(S, n)); }}// This code is contributed by Rohit_ranjan |
Javascript
<script>// javascript program for the// above approach // Function to return final result function minReqSubstring(s, n) { // Initialize variable to keep // track of ongoing sequence let ongoing = 'N'; let count = 0, l = s.length; for (let i = 1; i < l; i++) { // If current sequence is neither // increasing nor decreasing if (ongoing == 'N') { // If prev char is greater if (s[i] < s[i - 1]) { ongoing = 'D'; } // If prev char is same else if (s[i] == s[i - 1]) { ongoing = 'N'; } // Otherwise else { ongoing = 'I'; } } // If current sequence // is Non-Decreasing else if (ongoing == 'I') { // If prev char is smaller if (s[i] > s[i - 1]) { ongoing = 'I'; } // If prev char is same else if (s[i] == s[i - 1]) { // Update ongoing ongoing = 'I'; } // Otherwise else { // Update ongoing ongoing = 'N'; // Increase count count += 1; } } // If current sequence // is Non-Increasing else { // If prev char is greater, // then update ongoing with D if (s[i] < s[i - 1]) { ongoing = 'D'; } // If prev char is equal, then // update current with D else if (s[i] == s[i - 1]) { ongoing = 'D'; } // Otherwise, update ongoing // with N and increment count else { ongoing = 'N'; count += 1; } } } // Return count+1 return count + 1; } // Driver Code let S = "aeccdhba"; let n = S.length; document.write( minReqSubstring(S, n));// This code is contributed by target_2.</script> |
Output:
3
Time Complexity: O(N)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
