Dada una string que contiene solo (aumento) y (disminución). La tarea es devolver cualquier permutación de enteros [0, 1, …, N] donde N ≤ Longitud de S tal que para todo i = 0, …, N-1 :
- Si S[i] == “D”, entonces A[i] > A[i+1]
- Si S[i] == “I”, entonces A[i] < A[i+1].
Tenga en cuenta que la salida debe contener elementos distintos.
Ejemplos:
Entrada: S = “DDI”
Salida: [3, 2, 0, 1]
Entrada: S = “IDID”
Salida: [0, 4, 1, 3, 2]
Enfoque: Si S[0] == “I” , elija como primer elemento. Del mismo modo, si S[0] == “D” , elija como primer elemento. Ahora, para cada operación, elija el siguiente elemento máximo que no se haya elegido antes del rango [0, N] , y para la operación, elija el siguiente mínimo.
A continuación se muestra la implementación del enfoque anterior:
C++
//C++ Implementation of above approach #include<bits/stdc++.h> using namespace std; // function to find minimum required permutation void StringMatch(string s) { int lo=0, hi = s.length(), len=s.length(); vector<int> ans; for (int x=0;x<len;x++) { if (s[x] == 'I') { ans.push_back(lo) ; lo += 1; } else { ans.push_back(hi) ; hi -= 1; } } ans.push_back(lo) ; cout<<"["; for(int i=0;i<ans.size();i++) { cout<<ans[i]; if(i!=ans.size()-1) cout<<","; } cout<<"]"; } // Driver code int main() { string S = "IDID"; StringMatch(S); return 0; } //contributed by Arnab Kundu
Java
// Java Implementation of above approach import java.util.*; class GFG { // function to find minimum required permutation static void StringMatch(String s) { int lo=0, hi = s.length(), len=s.length(); Vector<Integer> ans = new Vector<>(); for (int x = 0; x < len; x++) { if (s.charAt(x) == 'I') { ans.add(lo) ; lo += 1; } else { ans.add(hi) ; hi -= 1; } } ans.add(lo) ; System.out.print("["); for(int i = 0; i < ans.size(); i++) { System.out.print(ans.get(i)); if(i != ans.size()-1) System.out.print(","); } System.out.print("]"); } // Driver code public static void main(String[] args) { String S = "IDID"; StringMatch(S); } } // This code is contributed by Rajput-Ji
Python
# Python Implementation of above approach # function to find minimum required permutation def StringMatch(S): lo, hi = 0, len(S) ans = [] for x in S: if x == 'I': ans.append(lo) lo += 1 else: ans.append(hi) hi -= 1 return ans + [lo] # Driver code S = "IDID" print(StringMatch(S))
C#
// C# Implementation of above approach using System; using System.Collections.Generic; class GFG { // function to find minimum required permutation static void StringMatch(String s) { int lo=0, hi = s.Length, len=s.Length; List<int> ans = new List<int>(); for (int x = 0; x < len; x++) { if (s[x] == 'I') { ans.Add(lo) ; lo += 1; } else { ans.Add(hi) ; hi -= 1; } } ans.Add(lo) ; Console.Write("["); for(int i = 0; i < ans.Count; i++) { Console.Write(ans[i]); if(i != ans.Count-1) Console.Write(","); } Console.Write("]"); } // Driver code public static void Main(String[] args) { String S = "IDID"; StringMatch(S); } } // This code is contributed by 29AjayKumar
Javascript
<script> // Javascript implementation of above approach // function to find minimum required permutation function StringMatch(s) { var lo=0, hi = s.length, len=s.length; var ans=[]; for (var x=0;x<len;x++) { if (s[x] == 'I') { ans.push(lo) ; lo += 1; } else { ans.push(hi) ; hi -= 1; } } ans.push(lo) ; document.write("["); for(var i=0;i<ans.length;i++) { document.write(ans[i]); if(i!=ans.length -1) document.write(", "); } document.write("]"); } var S = "IDID"; StringMatch(S); // This code is contributed by SoumikMondal </script>
[0, 4, 1, 3, 2]
Publicación traducida automáticamente
Artículo escrito por Sanjit_Prasad y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA