# Java O(n) clean solution easy to understand

• For example, given `IDIIDD` we start with sorted sequence `1234567`
Then for each `k` continuous `D` starting at index `i` we need to reverse `[i, i+k]` portion of the sorted sequence.

``````IDIIDD
1234567 // sorted
``````
``````    public int[] findPermutation(String s) {
int n = s.length(), arr[] = new int[n + 1];
for (int i = 0; i <= n; i++) arr[i] = i + 1; // sorted
for (int h = 0; h < n; h++) {
if (s.charAt(h) == 'D') {
int l = h;
while (h < n && s.charAt(h) == 'D') h++;
reverse(arr, l, h);
}
}
return arr;
}

void reverse(int[] arr, int l, int h) {
while (l < h) {
arr[l] ^= arr[h];
arr[h] ^= arr[l];
arr[l] ^= arr[h];
l++; h--;
}
}
``````

• The range you given in your description should have `k` as an offset (`i+k`), not as an absolute position.

• @TWiStErRob Yeah, my bad, I was thinking of length. Thanks.

• similar here but you can avoid back counting loop if you just keep track of the current count of 'D' and you can initialize the array during same pass, no need to fill out he array ahead of time.

``````    public int[] FindPermutation(string s)
{
int[] arr = new int[s.Length + 1];
arr[0] = 1;
int decreaseCnt = 0;
for (int i = 0; i < s.Length; i++, decreaseCnt++)
{
arr[i+1] = i + 2;
if (s[i] == 'I')
{
Reverse(arr, i - decreaseCnt, i);
decreaseCnt = -1;
}
}

Reverse(arr, arr.Length - 1 - decreaseCnt, arr.Length - 1);
return arr;
}

public void Reverse(int[] arr, int i, int j)
{
int temp = 0;
for (; i < j; i++, j--)
{
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
``````

• Thanks for sharing, very clear explanation.

• brilliant idea! I was working on heavy backtracking method and of course I got a TLE. Thanks for the idea, and I like the xor way to swap elements inside an array. Thanks

• ``````    public int[] findPermutation(String s) {
int n = s.length();
int[] res = new int[n + 1];
for(int i = 0; i < res.length; i++) res[i] = i + 1;
char[] sc = s.toCharArray();
for(int i = 0; i < n; i++){
if(sc[i] == 'D'){
int start = i;
while(i < n && sc[i] == 'D') i++;
reverse(res, start, i);
}
}
return res;
}

void reverse(int[] res, int start, int end){
while(start < end){
int temp = res[start];
res[start]  = res[end];
res[end] = temp;
start++;
end--;
}
}``````

• This post is deleted!

• Here is the solution without reverse:

``````public int[] findPermutation(String s) {
final int[] res = IntStream.rangeClosed(1, s.length() + 1).toArray();
for (int i = 0, len = s.length(); i < len;) {
int j = i;
while (j < len && s.charAt(j) == 'D') {
j++;
}
for (int k = j - i; k >= 0; k--, j--) {
res[i++] = j + 1;
}
}
return res;
}
``````

• For example, given `IDIIDD` we start with sorted sequence `1234567`
Then for each `k` continuous `D` starting at index `i` we need to reverse `[i, i+k]` portion of the sorted sequence.

``````IDIIDD
1234567 // sorted
``````
``````    public int[] findPermutation(String s) {
int n = s.length(), arr[] = new int[n + 1];
for (int i = 0; i <= n; i++) arr[i] = i + 1; // sorted
for (int h = 0; h < n; h++) {
if (s.charAt(h) == 'D') {
int l = h;
while (h < n && s.charAt(h) == 'D') h++;
reverse(arr, l, h);
}
}
return arr;
}

void reverse(int[] arr, int l, int h) {
while (l < h) {
arr[l] ^= arr[h];
arr[h] ^= arr[l];
arr[l] ^= arr[h];
l++; h--;
}
}
``````

Nice solution!
Mark the next `h` position with `nextH`

``````for (int h = 0; h < n; h++) {
if (s.charAt(h) == 'D') {
int l = h;
while (h < n && s.charAt(h) == 'D') h++;
int nextH = h;
reverse(arr, l, h);
h = nextH;
}
}
``````

which reduces half of `h` backtracking, useful when the continuous `h` is large

• how did you come up with such a genius idea?

• Thank you for your method!

``````class Solution {
public int[] findPermutation(String s) {
int[] array = new int[s.length()+1];
for(int i=0;i<array.length;i++){
array[i]=i+1;
}

for(int i=0;i<s.length();i++){
if(s.charAt(i)=='D'){
int h=i;
while(h<s.length()&&s.charAt(h)=='D'){
h++;
}
reverse(array,i,h);
i=h;
}
}

return array;
}

public void reverse(int[] array,int left,int right){
while(left<right){
int t = array[left];
array[left] = array[right];
array[right] = t;
left++;
right--;
}
}
}
``````

• Brilliant idea!

Here's my C++ version using STL methods.

``````class Solution {
public:
vector<int> findPermutation(string s) {
int n = (int)s.length() + 1;
vector<int> nums(n);
for (int i = 1; i <= n; ++i) nums[i - 1] = i;
for (int l = 0, h = 0; l < n - 1; l = h + 1) {
for (h = l; h < n - 1 && s[h] == 'D'; ++h);
reverse(nums.begin() + l, nums.begin() + h + 1);
}
return nums;
}
};
``````

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