1
class Solution {
2
 public:
3
  int numPermsDISequence(string s) {
4
    int n = s.length();
5
    queue<pair<string, unordered_set<int>>> q;
6
    unordered_set<int> v;
7
    string str = "";
8
    for (int i = 0; i <= n; ++i) {
9
      str = "";
10
      v.clear();
11
      str += (i + '0');
12
      v.insert(i);
13
      q.push({str, v});
14
    }
15
    int i = 0;
16
    unordered_set<string> visall;
17
    while (!q.empty()) {
18
      int sz = q.size();
19
      if (i == n) {
20
        return q.size();
21
      }
22
      while (sz--) {
23
        auto temp = q.front();
24
        q.pop();
25
        if (visall.find(temp.first) != visall.end()) {
26
          continue;
27
        }
28
        if (s[i] == 'D') {
29
          for (int j = temp.first.back() - '0' - 1; j >= 0; --j) {
30
            if (temp.second.find(j) == temp.second.end()) {
31
              temp.first += (j + '0');
32
              temp.second.insert(j);
33
              if (visall.find(temp.first) == visall.end()) {
34
                q.push({temp.first, temp.second});
35
              }
36
              temp.second.erase(j);
37
              temp.first.pop_back();
38
            }
39
          }
40
        } else {
41
          for (int j = temp.first.back() - '0' + 1; j <= n; ++j) {
42
            if (temp.second.find(j) == temp.second.end()) {
43
              temp.first += (j + '0');
44
              temp.second.insert(j);
45
              if (visall.find(temp.first) == visall.end()) {
46
                q.push({temp.first, temp.second});
47
              }
48
              temp.second.erase(j);
49
              temp.first.pop_back();
50
            }
51
          }
52
        }
53
      }
54
      i++;
55
    }
56
    return 0;
57
  }
58
};