Generar una array alternativa creciente y decreciente

Dada una string str de tamaño N que contiene solo dos tipos de caracteres que son «I» o «D» . La tarea es generar una array arr[0, 1, . . N] de tamaño N + 1 que cumplan las siguientes condiciones: 

• Si str[i] == “I” entonces arr[i] < arr[i+1]
• Si str[i] == “D” entonces arr[i] > arr[i+1]

Ejemplos: 

Entrada: str = “IDID” 
Salida: 0 4 1 3 2 
Explicación: 
str[0] == “I” por lo tanto arr[0] < arr[1] 
str[1] == “D” por lo tanto arr[1] > arr[2] 
str[2] == “I” por lo tanto arr[2] < arr[3] 
str[3] == “D” por lo tanto arr[3] > arr[4]

Entrada: str = “III” 
Salida: 0 1 2 3
 

Acercarse:

1. Inicialice la variable START como 0 y END como N .
2. Iterar sobre toda la array.
3. Si str[i] == “I”,  entonces asigne START en arr[i] e incremente el START .
4. Si str[i] == “D” , entonces asigne END en arr[i] y disminuya el END .
5. Ahora el último elemento de la array no está asignado, así que asigne START en A[N] .

A continuación se muestra la implementación del enfoque.  

// C++ program to Generate an increasing
// and decreasing array
 
#include <iostream>
using namespace std;
 
// Function that returns generated array
int* DiStirngMatch(string Str)
{
    int N = Str.length();
 
    // Dynamically allocate array
    int* arr = new int[N];
 
    // START=0, END=N
    int START = 0, END = N;
 
    // iterate over array
    for (int i = 0; i < N; i++) {
 
        // if Str[i]=='I' assign arr[i]
        // as START and increment START
        if (Str[i] == 'I')
            arr[i] = START++;
 
        // if str[i]=='D' assign arr[i]
        // as END and decrement END
        if (Str[i] == 'D')
            arr[i] = END--;
    }
 
    // assign A[N] as START
    arr[N] = START;
 
    // return starting
    // address of array A
    return arr;
}
 
// Driver Program
int main()
{
    string Str = "IDID";
    int N = Str.length();
    int* ptr = DiStirngMatch(Str);
    for (int i = 0; i <= N; i++)
        cout << ptr[i] << " ";
 
    return 0;
}

// Java program to generate an increasing
// and decreasing array
class GFG{
 
// Function that returns generated array
static int []DiStirngMatch(String Str)
{
    int N = Str.length();
 
    // Dynamically allocate array
    int []arr = new int[N + 1];
 
    // START=0, END=N
    int START = 0, END = N;
 
    // Iterate over array
    for(int i = 0; i < N; i++)
    {
         
        // if Str[i]=='I' assign arr[i]
        // as START and increment START
        if (Str.charAt(i) == 'I')
            arr[i] = START++;
 
        // if str[i]=='D' assign arr[i]
        // as END and decrement END
        if (Str.charAt(i) == 'D')
            arr[i] = END--;
    }
 
    // Assign A[N] as START
    arr[N] = START;
 
    // Return starting
    // address of array A
    return arr;
}
 
// Driver code
public static void main(String[] args)
{
    String Str = "IDID";
    int N = Str.length();
    int[] ptr = DiStirngMatch(Str);
     
    for(int i = 0; i <= N; i++)
        System.out.print(ptr[i] + " ");
}
}
 
// This code is contributed by amal kumar choubey

# Python3 program to generate an
# increasing and decreasing array
 
# Function that returns generated array
def DiStirngMatch(Str):
 
    N = len(Str)
 
    # Dynamically allocate array
    arr = (N + 1) * [0]
 
    # START, END= 0 ,N
    START, END = 0, N
 
    # Iterate over array
    for i in range (N):
 
        # If Str[i]=='I' assign arr[i]
        # as START and increment START
        if (Str[i] == 'I'):
            arr[i] = START
            START += 1
 
        # If str[i]=='D' assign arr[i]
        # as END and decrement END
        if (Str[i] == 'D'):
            arr[i] = END
            END -= 1
 
    # Assign A[N] as START
    arr[N] = START
     
    # Return starting
    # address of array A
    return arr
 
# Driver code
if __name__ == "__main__":
 
    Str = "IDID"
    N = len(Str)
    ptr = DiStirngMatch(Str)
     
    for i in range (N + 1):
        print(ptr[i], end = " ")
 
# This code is contributed by chitranayal

// C# program to generate an increasing
// and decreasing array
using System;
 
class GFG{
 
// Function that returns generated array
static int []DiStirngMatch(String Str)
{
    int N = Str.Length;
 
    // Dynamically allocate array
    int []arr = new int[N + 1];
 
    // START=0, END=N
    int START = 0, END = N;
 
    // Iterate over array
    for(int i = 0; i < N; i++)
    {
         
        // if Str[i]=='I' assign arr[i]
        // as START and increment START
        if (Str[i] == 'I')
            arr[i] = START++;
 
        // if str[i]=='D' assign arr[i]
        // as END and decrement END
        if (Str[i] == 'D')
            arr[i] = END--;
    }
 
    // Assign A[N] as START
    arr[N] = START;
 
    // Return starting
    // address of array A
    return arr;
}
 
// Driver code
public static void Main(String[] args)
{
    String Str = "IDID";
    int N = Str.Length;
    int[] ptr = DiStirngMatch(Str);
     
    for(int i = 0; i <= N; i++)
        Console.Write(ptr[i] + " ");
}
}
 
// This code is contributed by amal kumar choubey

<script>
 
// Javascript program to Generate an increasing
// and decreasing array
 
// Function that returns generated array
function DiStirngMatch( Str)
{
    var N = Str.length;
 
    // Dynamically allocate array
    var arr = Array(N).fill(0);
 
    // START=0, END=N
    var START = 0, END = N;
 
    // iterate over array
    for (var i = 0; i < N; i++) {
 
        // if Str[i]=='I' assign arr[i]
        // as START and increment START
        if (Str[i] == 'I')
            arr[i] = START++;
 
        // if str[i]=='D' assign arr[i]
        // as END and decrement END
        if (Str[i] == 'D')
            arr[i] = END--;
    }
 
    // assign A[N] as START
    arr[N] = START;
 
    // return starting
    // address of array A
    return arr;
}
 
// Driver Program
var Str = "IDID";
var N = Str.length;
var ptr = DiStirngMatch(Str);
for (var i = 0; i <= N; i++)
    document.write( ptr[i] + " ");
 
// This code is contributed by itsok.
</script>

0 4 1 3 2

Complejidad Temporal: O (N)  
Espacio Auxiliar: O (N)