We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Manhattan Distance After K Changes

Number: 3754

Difficulty: Medium

Paid? No

Companies: N/A

Problem Description

Given a string of moves (each being one of “N”, “S”, “E”, “W”) that describe a path from the origin on an infinite grid, you are allowed to change at most k characters (each change you can pick any of the four directions). As you traverse the string in order, you want to maximize the Manhattan distance (|x| + |y|) from the origin at some (intermediate) time. Find that maximum Manhattan distance that can be achieved after performing the allowed modifications.

Key Insights

  • The original string defines a “prefix‐path” (positions after each move) on the grid.
  • Without modifications each move contributes ±1 in one coordinate – the Manhattan distance after i moves is lower‐bounded by the “net” effect.
  • When allowed to change up to k characters, you can “flip” moves that are “counter‐productive” (e.g. a west step when you intend to go east) or even convert moves from one axis to the other (e.g. a vertical move becoming horizontal).
  • One good way to “boost” the distance is to choose a target quadrant (for example: “east–north” means we want x and y both to be nonnegative). Then, any move not consistent with that quadrant is a candidate for modification.
  • Converting a move that is directly “against” the chosen direction (for instance, a W when we want east) gives a net change of +2 along that coordinate (because its original effect was –1 but after modification it contributes +1).
  • Converting a move that originally affected only the “other” coordinate (say a vertical move when we need horizontal progress) gives +1 on that coordinate.
  • For any prefix we can (conceptually) decide how many modifications to “assign” to fix the horizontal part and how many to fix the vertical part; after modification the best we can do is “simulate” a monotonic path. (Note that even if we could “fix” all moves then the maximum Manhattan distance in i moves is i.)
  • Thus, for each prefix and for each of the four possible quadrant choices, we can compute the “base value” (the net distance without changes) and then see how many detrimental moves exist. Then by “allocating” a portion of modifications to horizontal and the remainder to vertical – prioritizing those moves that need a 2‐point “flip” (i.e. are directly contrary to the target) – we get a candidate Manhattan distance. (Finally, since every move is of unit length the best possible distance in a prefix of length i is capped by i.)
  • Iterating over all prefixes and all quadrant assignments lets us answer the question.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1) (apart from the input string; we only keep running counts for each prefix)

Solution

The idea is to simulate the path while “collecting” counts for each cardinal direction up to the current move. For each prefix (of length i) we record how many moves in that prefix went north, south, east and west. Then, consider each of the four quadrant “targets”:  • For horizontal movement, either we want to go east or west.  • For vertical movement, either we want to go north or south. For the chosen quadrant you decide:  – The “favorable” moves that already contribute positively to the desired net.  – The “detrimental” moves that go in the opposite direction. For example, consider target east for x. Let h_fav = count of ‘E’ and h_unfav = count of ‘W’ in the prefix. Then the “base” net horizontal is (h_fav – h_unfav). You can “fix” up to min(h_unfav, k) detrimental moves – each fix turns a –1 into +1 (a gain of 2) – and if modifications remain you may even convert some moves that originally affected only vertical motion (changing 0 into +1). Thus an “allocated” r modifications on the horizontal side give a horizontal displacement of   horizontal_val = (h_fav – h_unfav) + 2 * min(h_unfav, r) + (r – min(h_unfav, r)). Similarly for vertical with its own counts. For a given prefix and quadrant we “optimally” allocate modifications (it turns out that a good choice is to use as many modifications as needed to fix the moves going directly against the chosen side – up to the available k – and then assign the remainder to flip neutral (other‐axis) moves). Adding the “modified” horizontal and vertical displacements gives a candidate Manhattan distance. (Remember to cap the candidate by i since in i moves you cannot exceed i distance.) We then update our result as the maximum candidate value seen over all prefixes and quadrant choices.

Data structures used include simple integer counters (for N, S, E and W) and a few temporary variables. The algorithm does only one pass through the string.

Code Solutions

Below are code solutions in four languages with detailed line‐by‐line comments.

# Python solution
def maxManhattanDistance(s, k):
    # running counts for directions (prefix counts)
    countN = countS = countE = countW = 0
    ans = 0
    n = len(s)
    # iterate over each move (prefix index 0..n-1)
    for i in range(n):
        ch = s[i]
        # update counts accordingly
        if ch == 'N':
            countN += 1
        elif ch == 'S':
            countS += 1
        elif ch == 'E':
            countE += 1
        elif ch == 'W':
            countW += 1
        
        # For the current prefix of (i+1) moves, try all quadrant targets.
        # Each quadrant: horizontal target (east or west) and vertical target (north or south)
        for horizontal_target in ['E', 'W']:
            # set horizontal favorable/unfavorable counts
            if horizontal_target == 'E':
                h_fav, h_unfav = countE, countW
            else:  # target 'W'
                h_fav, h_unfav = countW, countE
            
            for vertical_target in ['N', 'S']:
                # set vertical favorable/unfavorable counts
                if vertical_target == 'N':
                    v_fav, v_unfav = countN, countS
                else:  # target 'S'
                    v_fav, v_unfav = countS, countN
                
                # current prefix length
                total_moves = i + 1
                
                # base displacement without changes for chosen quadrant
                base_horizontal = h_fav - h_unfav
                base_vertical = v_fav - v_unfav
                
                # For optimal allocation:
                # First use modifications to fix moves that directly oppose our target.
                # For horizontal: each fix gives a +2 boost.
                mod_for_h = min(h_unfav, k)
                # New horizontal displacement after fixing opposite moves
                horizontal_val = base_horizontal + 2 * mod_for_h
                # Any remaining modifications can be used on neutral moves 
                # (i.e. moves that did not contribute horizontally originally)
                rem_mod = k - mod_for_h
                horizontal_val += rem_mod  # each gives +1
                
                # Similarly for vertical
                mod_for_v = min(v_unfav, k)
                vertical_val = base_vertical + 2 * mod_for_v
                rem_mod_v = k - mod_for_v
                vertical_val += rem_mod_v
                
                # Total candidate Manhattan distance computed for this quadrant and prefix.
                candidate = horizontal_val + vertical_val
                # It cannot exceed the number of moves in this prefix.
                candidate = min(candidate, total_moves)
                ans = max(ans, candidate)
    return ans

# Example usage:
print(maxManhattanDistance("NWSE", 1))  # Expected output: 3
← Back to All Questions