• Time:O(n)
• Space:O(n)

C++

``````class Solution {
public:
vector<int> findPermutation(string s) {
vector<int> ans;
stack<int> stack;

for (int i = 0; i < s.length(); ++i) {
stack.push(i + 1);
if (s[i] == 'I')
while (!stack.empty())
ans.push_back(stack.top()), stack.pop();
}
stack.push(s.length() + 1);

while (!stack.empty())
ans.push_back(stack.top()), stack.pop();

return ans;
}
};
``````

JAVA

``````class Solution {
public int[] findPermutation(String s) {
int[] ans = new int[s.length() + 1];
int ansIndex = 0;
Deque<Integer> stack = new ArrayDeque<>();

for (int i = 0; i < s.length(); ++i) {
stack.push(i + 1);
if (s.charAt(i) == 'I')
while (!stack.isEmpty())
ans[ansIndex++] = stack.pop();
}
stack.push(s.length() + 1);

while (!stack.isEmpty())
ans[ansIndex++] = stack.pop();

return ans;
}
}
``````

Python

``````class Solution:
def findPermutation(self, s: str) -> List[int]:
ans = []
stack = []

for i, c in enumerate(s):
stack.append(i + 1)
if c == 'I':
while stack:  # consume all decreasings
ans.append(stack.pop())
stack.append(len(s) + 1)

while stack:
ans.append(stack.pop())

return ans
``````

• Time:O(n)
• Space:O(n)

C++

``````class Solution {
public:
vector<int> findPermutation(string s) {
vector<int> ans(s.length() + 1);

iota(begin(ans), end(ans), 1);

// for each D* group (s[i..j]), reverse ans[i..j + 1]
int i = -1;
int j = -1;

while (true) {
i = getNextIndex(s, 'D', j + 1);
if (i == s.length())
break;
j = getNextIndex(s, 'I', i + 1);
reverse(begin(ans) + i, begin(ans) + j + 1);
}

return ans;
}

private:
int getNextIndex(const string& s, char c, int start) {
for (int i = start; i < s.length(); ++i)
if (s[i] == c)
return i;
return s.length();
}
};
``````

JAVA

``````class Solution {
public int[] findPermutation(String s) {
int[] ans = new int[s.length() + 1];

for (int i = 0; i < ans.length; ++i)
ans[i] = i + 1;

// for each D* group (s[i..j]), reverse ans[i..j + 1]
int i = -1;
int j = -1;

while (true) {
i = getNextIndex(s, 'D', j + 1);
if (i == s.length())
break;
j = getNextIndex(s, 'I', i + 1);
reverse(ans, i, j);
}

return ans;
}

private int getNextIndex(final String s, char c, int start) {
for (int i = start; i < s.length(); ++i)
if (s.charAt(i) == c)
return i;
return s.length();
}

private void reverse(int[] A, int l, int r) {
while (l < r)
swap(A, l++, r--);
}

private void swap(int[] A, int i, int j) {
final int temp = A[i];
A[i] = A[j];
A[j] = temp;
}
}
``````

Python

``````class Solution:
def findPermutation(self, s: str) -> List[int]:
ans = [i for i in range(1, len(s) + 2)]

# for each D* group (s[i..j]), reverse ans[i..j + 1]
i = -1
j = -1

def getNextIndex(c: chr, start: int) -> int:
for i in range(start, len(s)):
if s[i] == c:
return i
return len(s)

while True:
i = getNextIndex('D', j + 1)
if i == len(s):
break
j = getNextIndex('I', i + 1)
ans[i:j + 1] = ans[i:j + 1][::-1]

return ans
``````