Beats 60%, Direct solution, O(n)
IntuitionJust go through the string s and get the best result.ApproachAt first add 4 auxiliary variables for the number of moving to the each of 4 directions:Th
# Intuition
Just go through the string `s` and get the best result.

# Approach
At first add 4 auxiliary variables for the number of moving to the each of 4 directions:
```
var Ns = 0;
var Ss = 0;
var Es = 0;
var Ws = 0;
```
Then go through the string `s` and get the best result:
```
for (int i = 0; i < s.Length; i++)
{
    switch (s[i])
    {
        case 'N':
            Ns++;
            break;
        case 'S':
            Ss++;
            break;
        case 'E':
            Es++;
            break;
        case 'W':
            Ws++;
            break;
    }
    var numOfKnees = GetNumOfKnees(Ns, Ss, Es, Ws);
    var manhattanDist = ManhattanDist(Ns, Ss, Es, Ws);
    var rs0 = Math.Min(numOfKnees, k) * 2 + manhattanDist;
    rs = Math.Max(rs, rs0);
}
```
2 auxiliary methods:
1. for the number of knees:
```
private int GetNumOfKnees(int Ns, int Ss, int Es, int Ws)
```
2. for the Manhattan distance:
```
private int ManhattanDist(int Ns, int Ss, int Es, int Ws)
```

# Complexity
- Time complexity:
$$O(n)$$

- Space complexity:
$$O(1)$$

# Code
```csharp []
public class Solution {
    public int MaxDistance(string s, int k) {
        var Ns = 0;
        var Ss = 0;
        var Es = 0;
        var Ws = 0;
        var rs = 0;
        for (int i = 0; i < s.Length; i++)
        {
            switch (s[i])
            {
                case 'N':
                    Ns++;
                    break;
                case 'S':
                    Ss++;
                    break;
                case 'E':
                    Es++;
                    break;
                case 'W':
                    Ws++;
                    break;
            }
            var numOfKnees = GetNumOfKnees(Ns, Ss, Es, Ws);
            var manhattanDist = ManhattanDist(Ns, Ss, Es, Ws);
            var rs0 = Math.Min(numOfKnees, k) * 2 + manhattanDist;
            rs = Math.Max(rs, rs0);
        }
        return rs;
    }
    private int GetNumOfKnees(int Ns, int Ss, int Es, int Ws)
    {
        var rs = Math.Min(Ns, Ss) + Math.Min(Es, Ws);
        return rs;
    }
    private int ManhattanDist(int Ns, int Ss, int Es, int Ws)
    {
        var rs = Math.Abs(Ns - Ss) + Math.Abs(Es - Ws);
        return rs;
    }
}
```
['C#']