Simple JAVA 10 lines 6 ms (93%) O(N) solution with explanation.


  • 0
    O

    The strategy is simple: when we see a "D", we don't do anything as long as we know where all the "D"s start. When we see an "I", we start to put the smallest available number i to this position and put i + 1 to its left until we reach the start of consecutive "D"s. In that way, we are putting any number as close to the left as possible.

    To give you some examples:
    For "DDI", since the numbers will be decreased twice, we can only start to put 1 into the array when the decreasing stops, i.e., when we see an "I" (or reaching the end of the string). We have to put 1 on the position of "I" and put 2 to the left and then put 3 to the left, resulting a "321" because of the presence of "DD" in the beginning.
    For "III", we don't need to worry about anything but just put 123 into the array.

    Eventually, however we need to remember to put the rest of numbers into the array backwards.

    public int[] findPermutation(String s) {
        int n = s.length(), num = 1, start = 0;
        char[] arr = s.toCharArray(); // It is always faster to change to char[] when str.charAt() will be called several times. 
        int[] res = new int[n + 1];
        for (int i = 0; i < n; i++) {
            if (arr[i] == 'I') {
                for (int j = i; j >= start; j--) { res[j] = num++; }
                start = i + 1;
            }
        }
        for (int j = n; j >= start; j--) { res[j] = num++; }
        return res;
    }

Log in to reply
 

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