Skip to content

942. DI String Match

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
 public:
  vector<int> diStringMatch(string s) {
    vector<int> ans;
    int mn = 0;
    int mx = s.length();

    for (const char c : s)
      ans.push_back(c == 'I' ? mn++ : mx--);
    ans.push_back(mn);

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
  public int[] diStringMatch(String s) {
    final int n = s.length();
    int[] ans = new int[n + 1];
    int mn = 0;
    int mx = n;

    for (int i = 0; i < n; ++i)
      ans[i] = s.charAt(i) == 'I' ? mn++ : mx--;
    ans[n] = mn;

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
  def diStringMatch(self, s: str) -> list[int]:
    ans = []
    mn = 0
    mx = len(s)

    for c in s:
      if c == 'I':
        ans.append(mn)
        mn += 1
      else:
        ans.append(mx)
        mx -= 1

    return ans + [mn]