# Python O(n) solution with stack

• To find the smallest lexicographical permutation, we start with a list of increasing order. All "I"s are already satisfied. With any sequence of continuous 'D''s, we reverse the list. Since the range of the numbers within the sequence is unchanged, the "I"'s are not influenced.

``````class Solution(object):
def findPermutation(self, s):
"""
:type s: str
:rtype: List[int]
"""

l = len(s)
stack,res = [],[]
for i in range (l):
cur_num = i+1
if s[i] == 'D':
stack.append(cur_num)
if s[i] == 'I':
stack.append(cur_num)
while stack:
res.append(stack.pop())
# last digit
res.append(l+1)
while stack:
res.append(stack.pop())

return res
``````

• Nice clean implementation! Java Version based on the same logic.

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

int len = s.length();

for (int i = 0; i < len; i++) {
int curr = i + 1;
if (s.charAt(i) == 'D') {
}

if (s.charAt(i) == 'I') {
while(!stack.isEmpty()) {
sol[index++] = stack.removeFirst();
}
}
}

sol[index++] = len + 1;
while (!stack.isEmpty())
sol[index++] = stack.removeFirst();

return sol;

}
}

``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.