# Solving Leetcode Interviews in Seconds with AI: DI String Match


	# Introduction
	In this blog post, we will explore how to solve the LeetCode problem "942" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like [Chatmagic](https://www.chatmagic.app), we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

	# Problem Statement
	> 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], and 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.   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 <= 105 s[i] is either 'I' or 'D'.  

	# Explanation
	Here's an efficient solution to reconstruct the permutation based on the given string `s`:

*   **Greedy Approach:** Maintain two pointers, `low` and `high`, initialized to 0 and n (length of s). Iterate through the string `s`. If `s[i]` is 'I', it signifies an increasing sequence. So, assign the current `low` value to the next element of the permutation `perm` and increment `low`. If `s[i]` is 'D', it signifies a decreasing sequence. So, assign the current `high` value to the next element of the permutation `perm` and decrement `high`.
*   **Final Element:** After iterating through the string, one element remains. Assign either the remaining `low` or `high` value (they are the same at this point) to the last element of `perm`. This completes the permutation reconstruction.

*   **Runtime and Storage Complexity:**
    *   Runtime: O(n), where n is the length of the string `s`.
    *   Storage: O(n) for the reconstructed permutation `perm`.

	
	# Code
	```python
	def reconstruct_permutation(s: str) -> list[int]:
    """
    Reconstructs a permutation perm of n + 1 integers based on the string s.

    Args:
        s: A string of length n where s[i] == 'I' if perm[i] < perm[i + 1],
           and s[i] == 'D' if perm[i] > perm[i + 1].

    Returns:
        A reconstructed permutation perm.
    """
    n = len(s)
    perm = [0] * (n + 1)
    low = 0
    high = n
    for i in range(n):
        if s[i] == 'I':
            perm[i] = low
            low += 1
        else:
            perm[i] = high
            high -= 1
    perm[n] = low  # or high, they are the same at this point
    return perm
	```