// find final vector dx dy
// change k negative parts
// SWWEW k=1
// . dy=-1
// ... dx=-2
// order doesn't matter
// NWSE . N E NWNE
// . W N
// . . .
// i solved the wrong problem, the MAX is ON the path, not final
// the order MATTER
we have to check each step
at each step remove the opposite to the maximum direction
Another clever intuition is min(total, dist + 2k):
each flip do +2
max flips we can do is total
Approach
pay attention to the description, don't solve the wrong problem
Complexity
Time complexity: $$O(n)$$
Space complexity: $$O(1)$$
Code
// 86ms
fun maxDistance(str: String, k: Int): Int {
var n = 0; var e = 0; var w = 0; var s = 0
return str.withIndex().maxOf { (i, c) ->
when (c) { 'N' -> ++n; 'S' -> ++s; 'W' -> ++w; 'E' -> ++e }
i + 1 - 2 * max(0, minOf(w + s, e + n, w + n, e + s) - k)
}
}
// 58ms
fun maxDistance(str: String, k: Int): Int {
var res = 0; var n = 0; var e = 0; var w = 0; var s = 0
for (c in str) {
when (c) { 'N' -> ++n; 'S' -> ++s; 'W' -> ++w; 'E' -> ++e }
if (e >= w && n >= s) {
val bad = max(0, w + s - k)
val good = w + s - bad
res = max(res, e + n - bad + good)
} else if (e < w && n < s) {
val bad = max(0, e + n - k)
val good = e + n - bad
res = max(res, w + s - bad + good)
} else if (e >= w && n < s) {
val bad = max(0, w + n - k)
val good = w + n - bad
res = max(res, e + s - bad + good)
} else {
val bad = max(0, e + s - k)
val good = e + s - bad
res = max(res, w + n - bad + good)
}
}
return res
}
// 90ms
pub fn max_distance(st: String, k: i32) -> i32 {
let (mut n, mut e, mut w, mut s) = (0, 0, 0, 0);
st.bytes().enumerate().map(|(i, c)| {
match (c) { b'N' => n += 1, b'S' => s += 1, b'E' => e += 1, _ => w += 1 }
i as i32 + 1 - 2 * 0.max((w + s).min(e + n).min(w + n).min(e + s) - k)
}).max().unwrap()
}
// 32ms
pub fn max_distance(st: String, k: i32) -> i32 {
let (mut n, mut e, mut w, mut s, mut r) = (0, 0, 0, 0, 0);
for (i, b) in st.bytes().enumerate() {
match (b) { b'N' => n += 1, b'S' => s += 1, b'E' => e += 1, _ => w += 1 }
r = r.max(i as i32 + 1 - 2 * 0.max((w + s).min(e + n).min(w + n).min(e + s) - k))
} r
}
// 31ms
pub fn max_distance(st: String, k: i32) -> i32 {
let (mut x, mut y, mut r) = (0i32, 0i32, 0);
for (i, b) in st.bytes().enumerate() {
match (b) { b'N' => y += 1, b'S' => y -= 1, b'E' => x += 1, _ => x -= 1 }
r = r.max((i as i32 + 1).min(x.abs() + y.abs() + 2 * k))
} r
}
// 22ms
int maxDistance(string s, int k) {
int x = 0, y = 0, r = 0, total = 1;
for (char c: s) {
y += (c == 'N') - (c == 'S'); x += (c == 'E') - (c == 'W');
r = max(r, min(total++, abs(x) + abs(y) + 2 * k));
} return r;
}
