LeetCode Entry
2833. Furthest Point From Origin
Max dist when replace with L or R
2833. Furthest Point From Origin easy substack youtube
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/1338
Problem TLDR
Max dist when replace _ with L or R
Intuition
The brute-force: replace all _ to R and check balance, then to L and check again. Some geometry transformation:_ + abs(R-L) = length-2*min(L,R) (see video explanation)
Approach
- asci %5 gives perfect 0,1,2 for _,L,R, do with that what you want
Complexity
-
Time complexity: \(O(n)\)
-
Space complexity: \(O(1)\)
Code
fun furthestDistanceFromOrigin(m: String) =
2*"LR".maxOf{c->m.count{it!=c}}-m.length
pub fn furthest_distance_from_origin(m: String) -> i32 {
(m.len()-2*m.matches('L').count().min(m.matches('R').count())) as _
}