3443. Maximum Manhattan Distance After K Changes Medium

1/**
2 * [3443] Maximum Manhattan Distance After K Changes
3 *
4 * You are given a string s consisting of the characters 'N', 'S', 'E', and 'W', where s[i] indicates movements in an infinite grid:
5 * 
6 * 	'N' : Move north by 1 unit.
7 * 	'S' : Move south by 1 unit.
8 * 	'E' : Move east by 1 unit.
9 * 	'W' : Move west by 1 unit.
10 * 
11 * Initially, you are at the origin (0, 0). You can change at most k characters to any of the four directions.
12 * Find the maximum Manhattan distance from the origin that can be achieved at any time while performing the movements in order.
13 * The Manhattan Distance between two cells (xi, yi) and (xj, yj) is |xi - xj| + |yi - yj|.
14 *  
15 * <strong class="example">Example 1:
16 * <div class="example-block">
17 * Input: <span class="example-io">s = "NWSE", k = 1</span>
18 * Output: <span class="example-io">3</span>
19 * Explanation:
20 * Change s[2] from 'S' to 'N'. The string s becomes "NWNE".
21 * <table style="border: 1px solid black;">
22 * 	<thead>
23 * 		<tr>
24 * 			<th style="border: 1px solid black;">Movement</th>
25 * 			<th style="border: 1px solid black;">Position (x, y)</th>
26 * 			<th style="border: 1px solid black;">Manhattan Distance</th>
27 * 			<th style="border: 1px solid black;">Maximum</th>
28 * 		</tr>
29 * 	</thead>
30 * 	<tbody>
31 * 		<tr>
32 * 			<td style="border: 1px solid black;">s[0] == 'N'</td>
33 * 			<td style="border: 1px solid black;">(0, 1)</td>
34 * 			<td style="border: 1px solid black;">0 + 1 = 1</td>
35 * 			<td style="border: 1px solid black;">1</td>
36 * 		</tr>
37 * 		<tr>
38 * 			<td style="border: 1px solid black;">s[1] == 'W'</td>
39 * 			<td style="border: 1px solid black;">(-1, 1)</td>
40 * 			<td style="border: 1px solid black;">1 + 1 = 2</td>
41 * 			<td style="border: 1px solid black;">2</td>
42 * 		</tr>
43 * 		<tr>
44 * 			<td style="border: 1px solid black;">s[2] == 'N'</td>
45 * 			<td style="border: 1px solid black;">(-1, 2)</td>
46 * 			<td style="border: 1px solid black;">1 + 2 = 3</td>
47 * 			<td style="border: 1px solid black;">3</td>
48 * 		</tr>
49 * 		<tr>
50 * 			<td style="border: 1px solid black;">s[3] == 'E'</td>
51 * 			<td style="border: 1px solid black;">(0, 2)</td>
52 * 			<td style="border: 1px solid black;">0 + 2 = 2</td>
53 * 			<td style="border: 1px solid black;">3</td>
54 * 		</tr>
55 * 	</tbody>
56 * </table>
57 * The maximum Manhattan distance from the origin that can be achieved is 3. Hence, 3 is the output.
58 * </div>
59 * <strong class="example">Example 2:
60 * <div class="example-block">
61 * Input: <span class="example-io">s = "NSWWEW", k = 3</span>
62 * Output: <span class="example-io">6</span>
63 * Explanation:
64 * Change s[1] from 'S' to 'N', and s[4] from 'E' to 'W'. The string s becomes "NNWWWW".
65 * The maximum Manhattan distance from the origin that can be achieved is 6. Hence, 6 is the output.
66 * </div>
67 *  
68 * Constraints:
69 * 
70 * 	1 <= s.length <= 10^5
71 * 	0 <= k <= s.length
72 * 	s consists of only 'N', 'S', 'E', and 'W'.
73 * 
74 */
75pub struct Solution {}
76
77// problem: https://leetcode.com/problems/maximum-manhattan-distance-after-k-changes/
78// discuss: https://leetcode.com/problems/maximum-manhattan-distance-after-k-changes/discuss/?currentPage=1&orderBy=most_votes&query=
79
80// submission codes start here
81
82impl Solution {
83    pub fn max_distance(s: String, k: i32) -> i32 {
84        0
85    }
86}
87
88// submission codes end
89
90#[cfg(test)]
91mod tests {
92    use super::*;
93
94    #[test]
95    fn test_3443() {
96    }
97}
98