static final int M = 1000000007;
public int checkRecord(int n) {
long[] PorL = new long[n + 1]; // ending with P or L, no A
long[] P = new long[n + 1]; // ending with P, no A
PorL[0] = P[0] = 1; PorL[1] = 2; P[1] = 1;
for (int i = 2; i <= n; i++) {
P[i] = PorL[i  1];
PorL[i] = (P[i] + P[i  1] + P[i  2]) % M;
}
long res = PorL[n];
for (int i = 0; i < n; i++) { // inserting A into (n1)length strings
long s = (PorL[i] * PorL[n  i  1]) % M;
res = (res + s) % M;
}
return (int) res;
}
dettier
@dettier
Posts made by dettier

Simple Java O(n) solution

RE: Python DP with explanation
Similar approach in Java.
static final int M = 1000000007; public int checkRecord(int n) { long[] PorL = new long[n + 1]; // ending in P or L, no A long[] P = new long[n + 1]; // ending in P, no A PorL[0] = P[0] = 1; PorL[1] = 2; P[1] = 1; for (int i = 2; i <= n; i++) { P[i] = PorL[i  1]; PorL[i] = (P[i] + P[i  1] + P[i  2]) % M; } long res = PorL[n]; for (int i = 0; i < n; i++) { // inserting A long s = (PorL[i] * PorL[n  i  1]) % M; res = (res + s) % M; } return (int) res; }

RE: Python, Straightforward [but slow] with Explanation
@awice Nice solution and implementation. I thought about a similar one, but decided that it wouldn't be accepted timewise. Honestly, I am surprised it worked because it is exponential. It can't handle the input like [1,2,1,2,1,2,...]. You are lucky it is not in the test cases :)

Short O(N) solution
This is a pretty common approach with static index variable.
let i = 0; var construct = function (s) { let numStr = []; while (s[i] === ''  s[i] >= '0' && s[i] <= '9') numStr.push(s[i++]); if (numStr.length === 0) return null; let node = new TreeNode(Number(numStr.join(''))); if (s[i] === '(') i++, node.left = construct(s), i++; if (s[i] === '(') i++, node.right = construct(s), i++; return node; } var str2tree = function(s) { i = 0; return construct(s); };

RE: Are there any others ppl solve the problems in Javascript?
@MichaelQQ Hi! I do everything is JS, except for when some specific data structures are needed. This week I didn't do that well, but sometimes I manage to get close to the top.

RE: Anyone want to discuss who hasn't figured this one out yet?
@georgeqwu Think of it this way  if the list [0...i] is unbalanced, what is the minimum amount of items should you remove from the beginning to make it balanced?

RE: why [0,0,11,5] needs 8 steps?...
@zyjdxtc Your first step is incorrect. A dress can be moved to an adjacent washing machine only.

RE: Anyone want to discuss who hasn't figured this one out yet?
@georgeqwu Hint: one loop is enough. Otherwise your idea seems correct.

Greedy O(n) JAVA solution with explanation
Idea is pretty simple. There are 2 possibilities:
 String starts with
"I"
. Then we should use 1 as the first item.  String starts with
"D..DI"
(k
letters) or the string is just"D...D"
. In this case we should usek, k  1, ..., 1
to get lexicographically smallest permutation.
Then we proceed computing the rest of the array. Also we should increase
min
variable that is used to store minimum value in remaining part of the array.public int[] findPermutation(String s) { s = s + "."; int[] res = new int[s.length()]; int min = 1, i = 0; while (i < res.length) { if (s.charAt(i) != 'D') { res[i++] = min++; } else { int j = i; while (s.charAt(j) == 'D') j++; for (int k = j; k >= i; k) res[k] = min++; i = j + 1; } } return res; }
 String starts with