Find Permutation — Leetcode 484

Original problem link: https://leetcode.com/problems/find-permutation/description/

In this problem, we are given a string of length n — 1 of I’s and D’s (increasing and decreasing respectively) and asked to return an array of length n of integers of the range [1, n] that matches the string description (increasing and decreasing at the correct indices). The returned array has to be the lowest lexicographically possible array.

This lends itself to a two-pointer approach since we can first fill the array with all increasing numbers from 1 to n by default, then find each range of consecutive decreases and reverse that part of the array to get the lexicographically lowest correct array.

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

        int index = 1;
        while (index < result.length) {
            if (s.charAt(index - 1) == 'D') {
                int start = index - 1;
                int end = index - 1;
                while (end + 1 < s.length() && s.charAt(end + 1) == 'D') {
                    end++;
                }
                end++;
                int endOfRange = end + 1;
                while (start < end) {
                    int temp = result[start];
                    result[start] = result[end];
                    result[end] = temp;
                    start++;
                    end--;
                }
                index = endOfRange;
            } else {
                index++;
            }
        }

        return result;
    }
}

The runtime is 2 ms and beats 99% of submissions in runtime.