DI String Match

LeetCode 979 | Difficulty: Easy

Easy

Problem Description

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]`.

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

Example 1:

Input: s = "IDID"
Output: [0,4,1,3,2]

Example 2:

Input: s = "III"
Output: [0,1,2,3]

Example 3:

Input: s = "DDI"
Output: [3,2,0,1]

Constraints:

- `1 <= s.length <= 10^5`

- `s[i]` is either `'I'` or `'D'`.

Topics: Array, Two Pointers, String, Greedy

---

Approach

Two Pointers

Use two pointers to traverse the array, reducing the search space at each step. This avoids the need for nested loops, bringing complexity from O(n²) to O(n) or O(n log n) if sorting is involved.

When to use

Array is sorted or can be sorted, and you need to find pairs/triplets that satisfy a condition.

Greedy

At each step, make the locally optimal choice. The challenge is proving the greedy choice leads to a global optimum. Look for: can I sort by some criterion? Does choosing the best option now ever hurt future choices?

When to use

Interval scheduling, activity selection, minimum coins (certain denominations), Huffman coding.

---

Solutions

Solution 1: C# (Best: 248 ms)

Metric	Value
Runtime	248 ms
Memory	31.9 MB
Date	2019-03-20

Solution

public class Solution {
    public int[] DiStringMatch(string S) {
        int N = S.Length;
    int[] result = new int[N+1];
    int left = 0, right = N;
    for (int i = 0; i < N; i++)
    {
        result[i] = (S[i]=='I') ? left++ : right--;
    }
    result[N] = left;
    return result; 
    }
}

---

Complexity Analysis

Approach	Time	Space
Two Pointers	$O(n)$	$O(1)$

---

Interview Tips

Key Points

• Start by clarifying edge cases: empty input, single element, all duplicates.
• Ask: "Can I sort the array?" — Sorting often enables two-pointer techniques.