3443. Maximum Manhattan Distance After K Changes
Approach
Track 4 direction counts; greedily flip least beneficial directions to maximize Manhattan distance.
Key Techniques
Array problems involve manipulating elements stored in a contiguous block of memory. Key techniques include two-pointer traversal, prefix sums, sliding windows, and in-place partitioning. In C#, arrays are zero-indexed and fixed in size — use List<T> when you need dynamic resizing.
Hash tables provide O(1) average-case lookup, insert, and delete. They are the go-to tool for counting frequencies, detecting complements (Two Sum pattern), and caching seen values. In C#, use Dictionary<K,V> for maps and HashSet<T> for membership checks.
Math problems test number theory, combinatorics, and modular arithmetic. Common tools: GCD/LCM (Euclidean algorithm), prime sieve, modular inverse (Fermat's little theorem), digit manipulation, and bit tricks. Overflow is a key concern in C# — use long when products may exceed 2³¹.
// Approach: Track 4 direction counts; greedily flip least beneficial directions to maximize Manhattan distance.
// Time: O(n) Space: O(1)
public class Solution
{
// Class level variables to store the character array and the integer k
private char[] directionArray;
private int k;
// Main method to find the maximum distance based on the given conditions
public int MaxDistance(string s, int k)
{
// Initialize the class variables
this.directionArray = s.ToCharArray();
this.k = k;
// Calculate maximum distances for each pair of directions
int max_SE = CalculateDistance('S', 'E');
int max_SW = CalculateDistance('S', 'W');
int max_NE = CalculateDistance('N', 'E');
int max_NW = CalculateDistance('N', 'W');
// Return the maximum distance among all calculated distances
return Math.Max(Math.Max(max_SE, max_SW), Math.Max(max_NE, max_NW));
}
// Helper method to calculate the distance for a given pair of directions
private int CalculateDistance(char direction1, char direction2)
{
int currentMax = 0; // Current running max distance
int maxDistance = 0; // Overall max distance found
int replacementCount = 0; // Count of non-direction characters replaced
// Iterate over each character in the direction array
foreach (char currentDirection in directionArray)
{
// Increment the current max if the character matches one of the interested directions
if (currentDirection == direction1 || currentDirection == direction2)
++currentMax;
else if (replacementCount < k) // Replace non-direction chars if replacements are available
{
++currentMax;
++replacementCount;
}
else
--currentMax; // Decrement the current max if no more replacements can be made
// Update the max distance if the current calculated distance is greater
maxDistance = Math.Max(maxDistance, currentMax);
}
return maxDistance; // Return the calculated max distance
}
}