Dada una string str , la tarea es encontrar el número mínimo de substrings en las que se puede dividir la string S dada, de modo que cada substring aumente o disminuya monótonamente.
Ejemplos:
Entrada: str = “abcdcba”
Salida: 2
Explicación:
La string se puede dividir en un mínimo de 2 substrings monótonas {“abcd”( aumentando ), “cba”( disminuyendo )}
Entrada: str = “aeccdhba”
Salida: 3
Explicación :
Las substrings generadas son {“ae”, “ccdh”, “ba”}
Enfoque: siga los pasos a continuación para resolver el problema:
- Inicialice una variable en curso = ‘N’ para realizar un seguimiento del orden de la secuencia actual.
- Itere sobre la string y para cada carácter, siga los pasos a continuación:
- Si en curso == ‘N’ :
- Si curr_character < prev_character , actualice en curso con D (no creciente).
- De lo contrario, si curr_character > prev_character , actualice en curso con I (no decreciente).
- De lo contrario, actualice en curso con N (ni No Creciente ni No Decreciente).
- De lo contrario, si está en curso == ‘I’ :
- Si curr_character > prev_character entonces actualice en curso con I .
- De lo contrario, si curr_character <prev_character , actualice en curso con N e incremente la respuesta.
- De lo contrario, actualice en curso con I .
- de lo contrario haz los siguientes pasos:
- Si curr_character < prev_character entonces actualice en curso con D .
- De lo contrario, si curr_character > prev_character , actualice en curso con N e incremente la respuesta.
- De lo contrario, actualice en curso con D .
- Finalmente, print answer+1 es la respuesta requerida.
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 return final result
int 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 Code
int 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 approach
import 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 code S = "aeccdhba" n = len(S) print(minReqSubstring(S, n)) # This code is contributed by Stuti Pathak
C#
// C# Program to implement
// the above approach
using 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>
Producción:
3
Complejidad temporal: O(N)
Espacio auxiliar: O(1)