πΉ Problem: 3443 Maximum Distance After K Operations
Difficulty: #Medium
Tags: #Greedy, #PrefixSum, #Simulation
π Problem Summary
You're given a string of directions like
'NSEW'. You can change up tokof them into another direction. After walking according to this possibly modified path, what's the maximum Manhattan distance you can end up from the origin?
π§ My Thought Process
Brute Force Idea:
I knew I had to somehow simulate all the directions and check how far they took me. I thought of trying every combination of up tokchanges to see what gave the farthest point, but that's exponential.Optimized Strategy:
I figured I could count occurrences ofN,S,E,W, then try to convertSintoN(or vice versa), and similarly forE/W, to maximize directional imbalance. I even understood that convertingS β Nboosts distance by+2...
But I wasn't 100% confident with how to distribute thekchanges between axes, so I looked up the solution.Algorithm Used:
[[greedy]] [[counter]] [[manhatten_distance]]
βοΈ Code Implementation (Python)
class Solution:
def maxDistance(self, s: str, k: int) -> int:
ans = 0
north = south = east = west = 0
for it in s:
if it == "N": north += 1
elif it == "S": south += 1
elif it == "E": east += 1
elif it == "W": west += 1
times1 = min(north, south, k)
times2 = min(east, west, k - times1)
ans = max(
ans,
self.count(north, south, times1) +
self.count(east, west, times2)
)
return ans
def count(self, d1: int, d2: int, ops: int) -> int:
return abs(d1 - d2) + 2 * ops # converting direction boosts distance by 2
β±οΈ Time & Space Complexity
- Time: O(n) β single pass through the string
- Space: O(1) β only counters used
π§© Key Takeaways
- β I learned that direction imbalance can be manipulated with a greedy strategy.
- π‘ Changing
S β Nincreases the imbalance by 2, not 1. - π Next time I see a Manhattan distance with limited moves/modifications, I'll think in terms of balancing and maximizing axis difference.
π Reflection (Self-Check)
- [x] Could I solve this without help? β Almost, but needed validation.
- [x] Did I write code from scratch? β Yes, then compared.
- [x] Did I understand why it works? β Fully after exploring the
+2gain. - [x] Will I be able to recall this in a week? β Definitely.
π Related Problems
- [[1162 As Far from Land as Possible]]
π Progress Tracker
| Metric | Value |
|---|---|
| Day | 25 |
| Total Problems Solved | 356 |
| Confidence Today | π |
Top comments (0)