Given a string str of size N containing two types of character only that are “I” or “D”. The task is to generate an array arr[0, 1, . . N] of size N + 1 satisfying the following conditions:
- If str[i] == “I” then arr[i] < arr[i+1]
- If str[i] == “D” then arr[i] > arr[i+1]
Examples:
Input: str = “IDID”
Output: 0 4 1 3 2
Explanation:
str[0] == “I” therefore arr[0] < arr[1]
str[1] == “D” therefore arr[1] > arr[2]
str[2] == “I” therefore arr[2] < arr[3]
str[3] == “D” therefore arr[3] > arr[4]Input: str = “III”
Output: 0 1 2 3
Approach:
- Initialize variable START as 0 and END as N.
- Iterate over the entire array.
- If str[i] == “I” then assign START at arr[i] and Increment the START.
- If str[i] == “D” then assign END at arr[i] and Decrement the END.
- Now the last element of the array isn’t assigned so assign START at A[N].
Below is the implementation of the approach.
C++
// C++ program to Generate an increasing// and decreasing array#include <iostream>using namespace std;// Function that returns generated arrayint* 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 Programint 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
// Java program to generate an increasing// and decreasing arrayclass GFG{// Function that returns generated arraystatic 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 codepublic 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
# Python3 program to generate an # increasing and decreasing array# Function that returns generated arraydef 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 codeif __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#
// C# program to generate an increasing// and decreasing arrayusing System;class GFG{// Function that returns generated arraystatic 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 codepublic 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 |
Javascript
<script>// Javascript program to Generate an increasing// and decreasing array// Function that returns generated arrayfunction 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 Programvar 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> |
Output:
0 4 1 3 2
Time Complexity: O (N)
Auxiliary Space: O (N)
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!
