Solve Stack Decoding and Fuel-Constrained Paths

You are given two independent coding tasks.

Task 1: Decode a Repeated-Pattern String

Given a valid encoded string, return its fully decoded form.

The encoding rule is: k[substring] means the substring inside the brackets should be repeated exactly k times. Encodings may be nested.

Examples:

• Input: 3[a]2[bc] → Output: aaabcbc
• Input: 3[a2[c]] → Output: accaccacc
• Input: 2[abc]3[cd]ef → Output: abcabccdcdcdef

Assume:

• The input string is valid.
• Repeat counts are positive integers.
• The decoded output length fits in memory.

Implement a function that returns the decoded string.

Task 2: Find the Shortest Grid Path With Refueling Stations

You are given an m x n grid. Each cell is one of the following:

• S: starting position
• T: target position
• .: empty cell
• #: blocked cell that cannot be entered
• G: gas station

You are also given an integer fuelCapacity. Moving one step up, down, left, or right costs 1 unit of fuel. You start at S with a full tank of fuelCapacity. When you enter a gas station cell G, your remaining fuel is reset to fuelCapacity. You may visit the same cell multiple times if your remaining fuel differs.

Return the minimum number of steps needed to reach T. If it is impossible, return -1.

Example:

grid = [
  "S..#",
  ".G.#",
  "...T"
]
fuelCapacity = 4

A valid solution should use BFS over states such as (row, col, remainingFuel), because reaching the same cell with more remaining fuel can lead to different future possibilities.

Part 1: Decode a Repeated-Pattern String

Given an encoded string s, decode it using the rule k[substring], where substring is repeated exactly k times. Repeat counts may have multiple digits, and encoded sections may be nested. The input is guaranteed to be valid. Return the fully decoded string. If s is empty, return an empty string.

Constraints

• 0 <= len(s) <= 100000
• s contains lowercase English letters, digits, and the characters '[' and ']'
• Repeat counts are positive integers
• The encoded string is valid
• The decoded output length fits in memory

Examples

Example 1

Input: '3[a]2[bc]'
Output: 'aaabcbc'

Explanation: 'a' is repeated 3 times and 'bc' is repeated 2 times.

Example 2

Input: '3[a2[c]]'
Output: 'accaccacc'

Explanation: First decode 'a2[c]' into 'acc', then repeat it 3 times.

Hints

1. Use one stack for repeat counts and another stack for the string built before each '['.
2. If the repeat count has multiple digits, keep building the number instead of treating each digit separately.

Part 2: Find the Shortest Grid Path With Refueling Stations

You are given a grid containing exactly one start cell 'S' and one target cell 'T'. Empty cells are '.', blocked cells are '#', and gas stations are 'G'. You start at 'S' with a full tank of fuelCapacity. Moving one step up, down, left, or right costs 1 unit of fuel. When you enter a gas station, your fuel is reset to fuelCapacity. Return the minimum number of steps needed to reach 'T', or -1 if it is impossible. Because arriving at the same cell with different remaining fuel can lead to different future options, the search state must include remaining fuel.

Constraints

• 1 <= m, n <= 60
• 1 <= fuelCapacity <= 100
• Each grid cell is one of 'S', 'T', '.', '#', or 'G'
• There is exactly one 'S' and exactly one 'T'
• You may revisit the same cell if the remaining fuel is different

Examples

Example 1

Input: (['S..#', '.G.#', '...T'], 4)
Output: 5

Explanation: A shortest valid route is S -> right -> down to G -> down -> right -> right to T.

Example 2

Input: (['ST'], 1)
Output: 1

Explanation: Edge case: the target is adjacent to the start.

Hints

1. A normal BFS over only (row, col) is not enough; include remaining fuel in the state.
2. After spending 1 fuel to move into a neighbor, reset fuel to fuelCapacity if that neighbor is a gas station.