> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/strings-arrays-and-2-pointers/find-permutation.md).

# Find Permutation

Given a positive integer `n` and a string `s` consisting only of letters *D* or *I*, you have to find any permutation of first `n` positive integer that satisfy the given input string.

*D* means the next number is smaller, while *I* means the next number is greater.

**Notes**

* Length of given string `s` will always equal to `n - 1`
* Your solution should run in linear time and space.

**Example :**

```
Input 1:

n = 3

s = ID

Return: [1, 3, 2]
```

```java
public class Solution {
    public ArrayList<Integer> findPerm(String A, int B) {
        int end = B, start = 1;
        ArrayList<Integer> ans = new ArrayList<>();
        for (int i = 0; i < A.length(); i++) {
            if (A.charAt(i) == 'I')
                ans.add(start++);
            else
                ans.add(end--);
        }
        if (A.charAt(A.length() - 1) == 'D')
            ans.add(start);
        else
            ans.add(end);
        return ans;
    }
}
```