DI String Match - Practice Coding Problems

DI String Match - Problem

A permutation perm of n + 1 integers of all the integers in the range [0, n] can be represented as a string s of length n where:

s[i] == 'I' if perm[i] < perm[i + 1]
s[i] == 'D' if perm[i] > perm[i + 1]

Given a string s, reconstruct the permutation perm and return it. If there are multiple valid permutations perm, return any of them.

Input & Output

Example 1 — Basic Pattern

$ Input: s = "IDID"

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

💡 Note: For 'I', use smallest available (0). For 'D', use largest (4). Continue: 'I'→1, 'D'→3, final→2. Result: 0<4, 4>1, 1<3, 3>2 matches IDID.

Example 2 — All Increasing

$ Input: s = "III"

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

💡 Note: All 'I' means strictly increasing sequence. Use numbers 0,1,2,3 in order: 0<1<2<3 matches III.

Example 3 — All Decreasing

$ Input: s = "DDI"

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

💡 Note: For 'D', use largest available. 'D'→3, 'D'→2, 'I'→0, final→1. Result: 3>2>0<1 matches DDI.

Constraints

1 ≤ s.length ≤ 10⁵
s consists of 'I' and 'D' only

Visualization

Tap to expand

Understanding the Visualization

Input Pattern

DI string specifies increase/decrease relationships

Greedy Assignment

Use extreme values to maximize flexibility

Valid Permutation

Resulting array satisfies all DI constraints

Key Takeaway

🎯 Key Insight: Use greedy assignment with two pointers - smallest for 'I', largest for 'D'

Asked in

G Google 15 M Microsoft 12 a Amazon 8

The key insight is to use a greedy two-pointer approach. For 'I', assign the smallest available number. For 'D', assign the largest. This ensures we always have valid choices remaining. Best approach is Two Pointers. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Two Pointers - Greedy Assignment	O(n)	O(1)	Use two pointers to assign smallest number for 'I' and largest for 'D'
Brute Force - Generate All Permutations	O((n+1)!)	O(n)	Generate all possible permutations and check which one matches the DI pattern
Greedy - Stack-Based Construction	O(n)	O(n)	Build result by processing patterns and using a stack for delayed decisions

Two Pointers - Greedy Assignment — Algorithm Steps

Step 1: Initialize low = 0, high = n (available number range)
Step 2: For each character, assign low++ for 'I' or high-- for 'D'
Step 3: Add the final remaining number to complete the permutation

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize Pointers

low = 0, high = n

Process Each Character

Assign low++ for 'I', high-- for 'D'

Add Final Number

low == high, add to complete permutation

Code -

solution.c — C

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

int* solution(char* s) {
    int n = strlen(s);
    int* result = malloc((n + 1) * sizeof(int));
    int low = 0, high = n;
    
    for (int i = 0; i < n; i++) {
        if (s[i] == 'I') {
            result[i] = low;
            low++;
        } else { // s[i] == 'D'
            result[i] = high;
            high--;
        }
    }
    
    // Add the last remaining number
    result[n] = low; // low == high at this point
    return result;
}

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

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through the string with constant operations

✓ Linear Growth

Space Complexity

O(1)

Only uses two pointer variables, output array doesn't count

✓ Linear Space

67.5K Views

Medium Frequency

~15 min Avg. Time

1.8K 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

Two Pointers - Greedy Assignment — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler