JavaScript O(n) solution


  • 0
    var findPermutation = function(s) {
        const counts = s.replace(/DI/g, 'D|I').replace(/ID/g, 'I|D').split('|').map(part => part.length);
        let maxSoFar = s[0] === 'D' ? counts[0] + 1 : 1;
        const res = [maxSoFar];
        for (let i = 0; i < counts.length; i++) {
            if (s[0] === 'D' && i % 2 === 0 || s[0] === 'I' && i % 2 === 1) {
                for (let j = maxSoFar - 1, stop = maxSoFar - counts[i]; j >= stop; j--) {
                    res.push(j);
                }
            } else {
                for (let stop = ++maxSoFar + counts[i] - 1; maxSoFar < stop; maxSoFar++) {
                    res.push(maxSoFar);
                }
                maxSoFar += counts[i + 1] || 0;
                res.push(maxSoFar);
            }
        }
        return res;
    };
    

Log in to reply
 

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