Python | TC: O(n) | SC: O(1) | Beats 100 %
IntuitionThe problem requires us to find the maximum Manhattan distance from the origin while traversing an infinite grid with given movement instructions. We c
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
The problem requires us to find the maximum Manhattan distance from the origin while traversing an infinite grid with given movement instructions. We can change at most k characters to any direction, which means we should strategically use these changes to maximize the distance.

A key observation is that opposite movements cancel each other (e.g., 'N' and 'S' or 'E' and 'W'). The goal is to maximize movement in one direction by either increasing its count or reducing the opposing movement count using k modifications.



# Approach
<!-- Describe your approach to solving the problem. -->

1. Count the frequency of each movement direction:
We maintain a dictionary d to store the count of 'N', 'S', 'E', and 'W'. As we traverse the string, we update these counts accordingly.

2. Calculate the net movement in each direction: 

    The majority movement in each axis (horizontal and vertical) determines the current Manhattan distance.

    The minority movement represents movements in the opposite direction, which reduces the effective distance.

3. Determine the distance lost and possible recovery:

    The distance lost is the sum of the minority movements (min_x + min_y), which could be countered by changing k characters.
    
    The distance recovered is the minimum of k and distance_lost, as we can flip up to k characters to favor movement in the majority direction.

4. Compute the maximum Manhattan distance:

    The achievable distance is computed as: 
*distance − distance lost + 2×distance recovered*
    
    We keep track of the maximum Manhattan distance encountered during the traversal.

# Complexity
- Time complexity: O(n)
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
    
We iterate over the string s once and perform constant-time calculations at each step.

- Space complexity: O(1)
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

We use only a fixed dictionary of size 4 (d), so space usage remains constant.

# Code
```python3 []
class Solution:
    def maxDistance(self, s: str, k: int) -> int:
        # Dictionary to store movement counts
        d = {'N': 0, 'S': 0, 'E': 0, 'W': 0}
        ans = 0

        for i in range(len(s)):
            d[s[i]] += 1  # Increment movement count

            # Determine movement contributions in both axes
            max_x, min_x = max(d['E'], d['W']), min(d['E'], d['W'])  # Horizontal movement
            max_y, min_y = max(d['N'], d['S']), min(d['N'], d['S'])  # Vertical movement

            # Compute the current Manhattan distance without changes
            distance = max_x + max_y  

            # Distance lost due to opposite movements canceling each other
            distance_lost = min_x + min_y  

            # Recover lost distance by modifying at most k characters
            distance_recovered = min(k, distance_lost)

            # Compute the maximum achievable Manhattan distance
            distance_acheivable = distance - distance_lost + 2 * distance_recovered

            # Update the answer with the maximum distance found so far
            ans = max(ans, distance_acheivable)

        return ans

```
['Python3']