Python3 - Consider every prefix
IntuitionIntuition:
The result must be a path starting from origin -> Path is a prefix of s
If we have no operations to use, then score of prefix s[:i] is given
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
# Intuition:
- The result must be a path starting from origin -> Path is a prefix of s
- If we have no operations to use, then score of prefix s[:i] is given by `abs(count("N")-count("S")) + abs(count("W")-count("E"))`
- If any moves have cancelled each other out, we can use an operation to increase the score by 2
- Consider every index `i` as the end of the prefix, and return the best one

# Complexity
- Time complexity: O(N)
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

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

# Code
```python3 []
class Solution:
    def maxDistance(self, s: str, k: int) -> int:
        char_to_count = defaultdict(int)
        best = 0
        for i, char in enumerate(s):
            char_to_count[char] += 1
            cur_score = abs(char_to_count["N"]-char_to_count["S"]) + abs(char_to_count["W"]-char_to_count["E"])
            best_score_ending_here = min(i+1, cur_score+k*2)
            best = max(best, best_score_ending_here)
        return best

```
['Python3']