Solve string merge and grid path tasks

Question

Given two equal-length strings s1 and s2, create a new string by iterating i = 0 … n-1, comparing s1[i] with s2[n-1-i]: append s1[i]; if the two characters are identical append that character again, otherwise append s2[n-1-i]. Examples: s1 = "abc", s2 = "def" → "afcd"; s1 = "abp", s2 = "jda" → "aaaapj"; s1 = "abp", s2 = "abp" → "appa". Return the resulting string. Design an algorithm for a robot moving on a 2-D grid containing: walls (impassable), healing cells (+health), and monster cells (–health). Starting with a given health value, find the shortest path from start to goal such that the robot’s health never drops to 0 or negative. Output that shortest distance (or the path itself). Solve an array/string problem that requires a sliding-window technique to meet a given constraint (details unspecified in the notes).

Crosswise String Merge

Constraints

• 0 <= n <= 200000, where n = len(s1) = len(s2)
• s1 and s2 must have equal length
• Characters may be any printable ASCII
• Aim for O(n) time and O(n) extra space

Examples

Example 1

Input: s1 = "abc", s2 = "def"
Output: afbecd

Explanation: i=0: 'a' vs 'f' -> append 'a','f'; i=1: 'b' vs 'e' -> append 'b','e'; i=2: 'c' vs 'd' -> append 'c','d'.

Example 2

Input: s1 = "abp", s2 = "jda"
Output: aabdpj

Explanation: i=0: 'a' vs 'a' equal -> append 'a','a'; i=1: 'b' vs 'd' -> 'b','d'; i=2: 'p' vs 'j' -> 'p','j'.

Hints

1. Use j = n - 1 - i to index s2 from the end while scanning s1 from the start.
2. Build the result with a list of characters and join at the end for efficiency.
3. Handle the empty-string case (n = 0) by returning an empty string.

Approach

Traverse s1 left-to-right while pairing each character s1[i] with s2[n-1-i]. Append s1[i] and then either the same character again if they match or s2[n-1-i] otherwise. Using a list for accumulation ensures O(n) time and O(n) space.

• Time complexity: O(n)
• Space complexity: O(n)