Find Permutation - Practice Coding Problems

Find Permutation - Problem

A permutation perm of n integers containing all integers from 1 to n can be represented as a string s of length n - 1 where:

s[i] == 'I' if perm[i] < perm[i + 1] (Increasing)
s[i] == 'D' if perm[i] > perm[i + 1] (Decreasing)

Given a string s, reconstruct the lexicographically smallest permutation perm and return it.

Lexicographically smallest means the permutation that would appear first in dictionary order.

Input & Output

Example 1 — Basic Pattern

$ Input: s = "DI"

› Output: [3,1,2]

💡 Note: For pattern 'DI', we need perm[0] > perm[1] < perm[2]. The lexicographically smallest such permutation is [3,1,2]: 3 > 1 < 2.

Example 2 — All Increasing

$ Input: s = "III"

› Output: [1,2,3,4]

💡 Note: For pattern 'III', we need all increasing: perm[0] < perm[1] < perm[2] < perm[3]. The answer is simply [1,2,3,4].

Example 3 — All Decreasing

$ Input: s = "DD"

› Output: [3,2,1]

💡 Note: For pattern 'DD', we need all decreasing: perm[0] > perm[1] > perm[2]. The lexicographically smallest is [3,2,1].

Constraints

1 ≤ s.length ≤ 10⁵
s[i] is either 'I' or 'D'

Visualization

Tap to expand

Understanding the Visualization

Input

Pattern string 'DI' representing decrease-increase

Process

Start with sorted array and reverse D segments

Output

Lexicographically smallest valid permutation

Key Takeaway

🎯 Key Insight: Start with sorted order and reverse only the segments that need to be decreasing

Asked in

G Google 25 f Facebook 18 a Amazon 15 M Microsoft 12

The key insight is that we can start with the lexicographically smallest array [1,2,3,...,n] and reverse segments where we see consecutive 'D' patterns. The greedy approach gives us the optimal solution in O(n) time and O(1) extra space.

Common Approaches

Approach	Time	Space	Notes
✓ Generate All Permutations	O((n+1)!)	O((n+1)!)	Generate all possible permutations and find the lexicographically smallest one that matches the pattern
Greedy Reversal	O(n)	O(1)	Start with sorted array and reverse segments wherever we see 'D' patterns
Stack-Based Construction	O(n)	O(n)	Use a stack to build the permutation by strategically placing numbers based on I/D patterns

Generate All Permutations — Algorithm Steps

Generate all permutations of numbers 1 to n+1
For each permutation, check if it matches the I/D pattern
Return the lexicographically smallest matching permutation

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate

Create all permutations of [1,2,3]

Test

Check each against pattern 'DI'

Select

Return first valid permutation

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

bool isValid(int* perm, int n, char* s) {
    for (int i = 0; i < strlen(s); i++) {
        if (s[i] == 'I' && perm[i] >= perm[i + 1]) return false;
        if (s[i] == 'D' && perm[i] <= perm[i + 1]) return false;
    }
    return true;
}

void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

bool nextPermutation(int* arr, int n) {
    int i = n - 2;
    while (i >= 0 && arr[i] >= arr[i + 1]) i--;
    if (i < 0) return false;
    
    int j = n - 1;
    while (arr[j] <= arr[i]) j--;
    swap(&arr[i], &arr[j]);
    
    for (int k = i + 1, l = n - 1; k < l; k++, l--) {
        swap(&arr[k], &arr[l]);
    }
    return true;
}

int* solution(char* s, int* returnSize) {
    int n = strlen(s) + 1;
    int* result = (int*)malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) {
        result[i] = i + 1;
    }
    
    do {
        if (isValid(result, n, s)) {
            *returnSize = n;
            return result;
        }
    } while (nextPermutation(result, n));
    
    *returnSize = 0;
    return result;
}

int main() {
    char s[1000];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    
    int returnSize;
    int* result = solution(s, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O((n+1)!)

Generating all permutations takes factorial time

✓ Linear Growth

Space Complexity

O((n+1)!)

Storing all permutations requires factorial space

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Generate All Permutations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler