Solve three coding interview problems

Part 1: Nested String Decoder

Given an encoded string where patterns are formatted as k[string], where the string inside the brackets is repeated exactly k times, return the decoded string. You may assume the input is always valid.

def decode_string(s: str) -> str:

Example: Input: s = "3[a]2[bc]" Output: "aaabcbc"

Part 2: Max Profit with Cooldown

Given an array prices where prices[i] is the price of a stock on day i, find the maximum profit you can achieve. You may complete as many transactions as you like, but you must sell before you buy again, and there is a 1-day cooldown period after selling (i.e., you cannot buy on the day after you sell).

def max_profit(prices: list[int]) -> int:

Example: Input: prices = [1, 2, 3, 0, 2] Output: 3 (Buy, Sell, Cooldown, Buy, Sell)

Part 3: Number of Islands

Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically.

def num_islands(grid: list[list[str]]) -> int:

Example: Input: grid = [["1","1","0"],["1","1","0"],["0","0","1"]] Output: 2