@yuxiangmusic said in Java O(n) clean solution easy to understand:

For example, given IDIIDD we start with sorted sequence 1234567

IDIIDD 1234567 // sorted 1324765 // answer 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--; } }

Then for each k continuous D starting at index i we need to reverse [i, i+k] portion of the sorted sequence.

Nice solution!

Mark the next h position with nextH

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