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, 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

    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