We want to construct a permutation of [0, n] such that for each character in s:
If s[i] == ‘I’, then perm[i] < perm[i+1]
If s[i] == ‘D’, then perm[i] > perm[i+1]
The greedy way is to use two pointers: one starting at 0 (lo), one at n (hi). For each ‘I’, pick lo and increment; for each ‘D’, pick hi and decrement. This guarantees the required order.
classSolution {
publicint[]diStringMatch(String s) {
int n = s.length(), lo = 0, hi = n;
int[] ans =newint[n+1];
for (int i = 0; i < n; ++i) {
ans[i]= s.charAt(i) =='I'? lo++ : hi--;
}
ans[n]= lo;
return ans;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
classSolution {
fundiStringMatch(s: String): IntArray {
val n = s.length
var lo = 0var hi = n
val ans = IntArray(n+1)
for (i in s.indices) {
ans[i] = if (s[i] =='I') lo++else hi-- }
ans[n] = lo
return ans
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
classSolution:
defdiStringMatch(self, s: str) -> list[int]:
n = len(s)
lo, hi =0, n
ans = []
for c in s:
if c =='I':
ans.append(lo)
lo +=1else:
ans.append(hi)
hi -=1 ans.append(lo)
return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
impl Solution {
pubfndi_string_match(s: String) -> Vec<i32> {
let n = s.len();
let (mut lo, mut hi) = (0, n asi32);
letmut ans = Vec::with_capacity(n+1);
for c in s.chars() {
if c =='I' {
ans.push(lo);
lo +=1;
} else {
ans.push(hi);
hi -=1;
}
}
ans.push(lo);
ans
}
}